Description

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

Input Format

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.

Output Format

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

4 5 
1 
2 
8 
2 

3 

Hint

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