Question

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 1

"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.

"