#P4012. 奶牛飞盘队 Cow Frisbee Team
奶牛飞盘队 Cow Frisbee Team
Description
老唐最近迷上了飞盘,约翰想和他一起玩,于是打算从他家的N头奶牛中选出一支队伍。每只奶牛的能力为整数,第i头奶牛的能力为Ri 。飞盘队的队员数量不能少于 1、大于N。一支队伍的总能力就是所有队员能力的总和。
约翰比较迷信,他的幸运数字是F,所以他要求队伍的总能力必须是F的倍数。请帮他算一下,符合这个要求的队伍组合有多少?由于这个数字很大,只要输出答案除以10^8的余数就可以了。
Input Format
第一行:两个用空格分开的整数:N和F,1 ≤ N ≤ 2000,1 ≤ F ≤ 1000
第二行到N + 1行:第i + 1行有一个整数Ri ,表示第i头奶牛的能力,1 ≤ Ri ≤ 10^5
Output Format
第一行:单个整数,表示方案数除以10^8的余数
Sample
Input
4 5
1
2
8
2
Output
3
Hint
Hint
有两种方案都是8 + 2 = 10,只是选的奶牛不一样,第三种方案是2 + 2 + 1 = 5
Source
USACO 2009 Mar