说明

Farmer Han开始玩飞盘之后，YDS也打算让奶牛们享受飞盘的乐趣

他要组建一只奶牛飞盘队．他的$N(1≤N≤2000)$只奶牛，每只奶牛有一个飞盘水准指数$R_i(1≤R_i≤100000)$

YDS要选出1只或多于1只奶牛来参加他的飞盘队．由于YDS的幸运数字是$F(1≤F≤1000)$，他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数

帮YDS算算一共有多少种组队方式．组队方式数模$10^8$取余的结果

输入格式

第1行输入$N$和$F$，之后$N$行输入$R_i$

输出格式

组队方式数模$10^8$取余的结果

样例

4 5 
1
2 
8 
2

3