牛飞盘队Cow Frisbee Team

老唐最近迷上了飞盘，约翰想和他一起玩，于是打算从他家的N头奶牛中选出一支队伍。
每只奶牛的能力为整数，第i头奶牛的能力为R i 。飞盘队的队员数量不能少于 1、大于N。
一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信，他的幸运数字是F，所以他要求队伍的总能力必须是F的倍数。请帮他
算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案除以 10^8的余
数就可以了。
输入格式
第一行：两个用空格分开的整数：N和F，1≤N≤2000，1≤F≤1000
第二行到N+1行：第i+1行有一个整数Ri ，表示第i头奶牛的能力，1 ≤Ri≤10^5
输出格式
 第一行：单个整数,表示方案数除以 10^8的余数
样例 
4 5 1 2 8 2 3 （有两种方案都是8 + 2 = 10，只是选的奶牛）
题目描述
农夫顿因开始玩飞盘之后，约翰也打算让奶牛们享受飞盘的乐趣．他要组建一只奶牛飞盘
队．他的N(1≤N≤2000)只奶牛，每只部有一个飞盘水准指数Ri(1≤Ri≤100000)．约翰要选出1只或多于1只奶牛来参加他的飞盘队．由于约翰的幸运数字是F(1≤F≤1000)，他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数．
帮约翰算算一共有多少种组队方式．
输入输出格式
输入格式：
* Line 1: Two space-separated integers: N and F
* Lines 2..N+1: Line i+1 contains a single integer: R_i
输出格式：
* Line 1: A single integer representing the number of teams FJ can choose, modulo 100,000,000.
输入输出样例
输入样例#1： 
4 5 
1 
2 
8 
2 
输出样例#1： 
3 
说明
FJ has four cows whose ratings are 1, 2, 8, and 2. He will only accept a team whose rating sum is a multiple of 5.
FJ can pair the 8 and either of the 2's (8 + 2 = 10), or he can use both 2's and the 1 (2 + 2 + 1 = 5).