#4756. [USACO09MAR]Cow Frisbee Team S

[USACO09MAR]Cow Frisbee Team S

当前没有测试数据。

[USACO09MAR]Cow Frisbee Team S

题目描述

老唐最近迷上了飞盘,约翰想和他一起玩,于是打算从他家的 NN 头奶牛中选出一支队伍。

每只奶牛的能力为整数,第 ii 头奶牛的能力为RiR_i 。飞盘队的队员数量不能少于 11、大于NN。一支队伍的总能力就是所有队员能力的总和。

约翰比较迷信,他的幸运数字是 FF ,所以他要求队伍的总能力必须是 FF 的倍数。请帮他

算一下,符合这个要求的队伍组合有多少?由于这个数字很大,只要输出答案对 10810^8 取模的值。

输入格式

第一行:两个用空格分开的整数:NNFF

第二行到 N+1N+1 行:第 i+1i+1 行有一个整数RiR_i ,表示第 ii 头奶牛的能力。

输出格式

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

样例 #1

样例输入 #1

4 5 
1 
2 
8 
2

样例输出 #1

3

提示

数据范围与约定

  • 对于 100%100\% 的数据,1N20001 \le N \le 20001F10001 \le F \le 10001Ri1051 \le R_i \le 10^5