题目描述

小珅最近迷上了飞盘，小泽想和他一起玩，于是打算从他家的 N 头奶牛中选出一支队伍。

每只奶牛的能力为整数，第 i 头奶牛的能力为 R_i。飞盘队的队员数量不能少于 1、大于 N。一支队伍的总能力就是所有队员能力的总和。

小泽比较迷信，他的幸运数字是 F，所以他要求队伍的总能力必须是 F 的倍数。请帮他算一下，符合这个要求的队伍组合有多少？由于这个数字很大，只要输出答案对 10^8 取模的值。

输入格式

第 1 行：两个用空格分开的整数：N 和 F。

第 2 行到 N+1 行：第 i+1 行有一个整数 R_i，表示第 i 头奶牛的能力。

输出格式

第 1 行：1 个整数，表示方案数对 10^8 取模的值。

输入样例 #1

4 5
1
2
8
2

输出样例 #1

3

输入样例 #2

5 7
2
6
1
7
8

输出样例 #2

5

输入样例 #3

3 3
1
2
3

输出样例 #3

3

数据范围与约定

对于 100% 的数据，1≤N≤2000，1≤F≤1000，1≤R_i≤10^5。