Flying Disc Team Combinations

Old Tang has become obsessed with flying disc. His friend John wants to play with him by selecting a team from the N cows at Tang's farm. Each cow has an integer ability and the i-th cow's ability is given by \(R_i\). A team must consist of at least one cow and at most N cows. The total ability of a team is defined as the sum of the abilities of all its members.

John is superstitious and his lucky number is \(F\). Therefore, he requires that the team's total ability is a multiple of \(F\). Your task is to count how many teams satisfy this requirement. Since the answer might be very large, print the answer modulo \(10^8\).

Note: A team corresponds to any non-empty subset of cows.

inputFormat

The first line contains two integers \(N\) and \(F\) separated by a space, where \(1 \leq N \leq 10^5\) (or as specified) and \(F\) is the lucky number.

The second line contains \(N\) integers \(R_1, R_2, \ldots, R_N\) representing the ability of each cow.

outputFormat

Output a single integer, which is the number of valid teams whose total ability is a multiple of \(F\), taken modulo \(10^8\).

sample

3 3
1 2 3

4