[USACO09MAR]Cow Frisbee Team S

题目描述

老唐最近迷上了飞盘,约翰想和他一起玩,于是打算从他家的 $N$ 头奶牛中选出一支队伍。 每只奶牛的能力为整数,第 $i$ 头奶牛的能力为$R_i$ 。飞盘队的队员数量不能少于 $1$、大于$N$。一支队伍的总能力就是所有队员能力的总和。 约翰比较迷信,他的幸运数字是 $F$ ,所以他要求队伍的总能力必须是 $F$ 的倍数。请帮他 算一下,符合这个要求的队伍组合有多少?由于这个数字很大,只要输出答案对 $10^8$ 取模的值。

输入输出格式

输入格式


第一行:两个用空格分开的整数:$N$ 和 $F$。 第二行到 $N+1$ 行:第 $i+1$ 行有一个整数$R_i$ ,表示第 $i$ 头奶牛的能力。

输出格式


第一行:单个整数,表示方案数对 $10^8$ 取模的值。

输入输出样例

输入样例 #1

4 5 
1 
2 
8 
2 

输出样例 #1

3 

说明

#### 数据范围与约定 - 对于 $100\%$ 的数据,$1 \le N \le 2000$,$1 \le F \le 1000$ ,$1 \le R_i \le 10^5$ 。