You are given a set of N positive integers and another integer P, wher

1.	You are given a set of N positive integers and another integer P, where P is a small prime. You need to write a program to count the number of subsets of size (cardinality) 3, the sum of whose elements is divisible by P. Since the number K of such sets can be huge, output K modulo 10007 1009 (the remainder when K is divided by 1009)
Answer» <P>"Constraints N <= 500 P<50 All INTEGERS <=1000 Input Format First line two comma separated integers N, P The next line contains N comma separated integers Output One integer GIVING the number of subsets the sum of whose elements is DIVISIBLE by P. Give result modulo 1009 Input 5,5 3,7,12,13,15 Output 4 Explanation There are 4 subsets of size 3 with sum a multiple of 5: {3, 7, 15}, {12, 13, 15}, {7, 13, 15}, {3, 12, 15}, Hence the output is 4. "

You are given a set of N positive integers and another integer P, where P is a small prime. You need to write a program to count the number of subsets of size (cardinality) 3, the sum of whose elements is divisible by P. Since the number K of such sets can be huge, output K modulo 10007 1009 (the remainder when K is divided by 1009)

Answer»

<P>"Constraints

N <= 500

P<50

All INTEGERS <=1000

Input Format

First line two comma separated integers N, P

The next line contains N comma separated integers

Output

One integer GIVING the number of subsets the sum of whose elements is DIVISIBLE by P. Give result modulo 1009

Input

5,5

3,7,12,13,15

Output

Explanation

There are 4 subsets of size 3 with sum a multiple of 5: {3, 7, 15}, {12, 13, 15}, {7, 13, 15}, {3, 12, 15}, Hence the output is 4.