Cow Frisbee Team

Interview

Time limit1sMemory limit128 MB

Summary

Count the nonempty subsets of N cows whose rating sum is divisible by F, modulo 100000000.

Level: Medium6 of 10
Topics: Dynamic programming, Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

After Farmer Don took up Frisbee, Farmer John (FJ) wanted to join in the fun. He wants to form a Frisbee team from his $N$ cows ( $1 \le N \le 2000$ ), conveniently numbered $1 \ldots N$ . Each cow $i$ has a rating $R_i$ ( $1 \le R_i \le 100000$ ) denoting her skill at playing Frisbee. FJ can form a team by choosing one or more of his cows.

However, because FJ is very selective when forming Frisbee teams, he adds one more constraint. His favorite number is $F$ ( $1 \le F \le 1000$ ), and he will only accept a team if the sum of the ratings of the cows on it is exactly divisible by $F$ .

Help FJ find how many different teams he can choose. Two cows are always distinct, so teams made of different cows count separately even when their ratings match. Because this number can be very large, output the answer modulo $100000000$ .

Input

Line $1$ : Two space-separated integers, $N$ and $F$ .
Lines $2 \ldots N+1$ : Line $i+1$ contains a single integer, $R_i$ .

Output

Line $1$ : A single integer, the number of teams FJ can choose, modulo $100000000$ .

Hint

In the example above, FJ can pair the $8$ with either of the two $2$ 's ( $8 + 2 = 10$ ), or he can use both $2$ 's together with the $1$ ( $2 + 2 + 1 = 5$ ). Because there are two cows rated $2$ , the $8 + 2$ combination counts as two distinct teams.

Examples3

Example 1
Input
```
4 5
1
2
8
2
```
Expected output
```
3
```
Example 2
Input
```
1 5
5
```
Expected output
```
1
```
Example 3
Input
```
1 7
5
```
Expected output
```
0
```