P2946 [USACO09MAR] Cow Frisbee Team S

Lao Tang has recently gotten into frisbee, and John wants to play with him, so he plans to select a team from his $N$ cows. Each cow has an integer ability. The $i$-th cow’s ability is $R_i$. The number of players on the frisbee team must be between $1$ and $N$ inclusive. A team’s total ability is the sum of the abilities of all its members. John is superstitious, and his lucky number is $F$, so he requires the team’s total ability to be a multiple of $F$. Please compute how many team selections satisfy this requirement. Since this number can be very large, output the answer modulo $10^8$.

The first line contains two space-separated integers: $N$ and $F$. Lines $2$ through $N+1$: line $i+1$ contains an integer $R_i$, the ability of the $i$-th cow.

A single integer: the number of valid selections modulo $10^8$.

For $100\%$ of the testdata, $1 \le N \le 2000$, $1 \le F \le 1000$, $1 \le R_i \le 10^5$. Translated by ChatGPT 5