题目描述

农夫顿因开始玩飞盘之后，约翰也打算让奶牛们享受飞盘的乐趣．他要组建一只奶牛飞盘队．

他的$\red{N(1≤}$$\red{N≤}$$\red{2000)}$只奶牛，每只部有一个飞盘水准指数$\red{Ri(1≤}$$\red{Ri≤}$$\red{100000)}$．约翰要选出$\red{1}$只或多于$\red{1}$只奶 牛来参加他的飞盘队．由于约翰的幸运数字是$\red{F(1≤}$$\red{F≤}$$\red{1000)，}$他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数．

帮约翰算算一共有多少种组队方式．

输入格式

第$\red{1}$行输入$\red{N}$和$\red{F}$

之后$\red{N}$行输入$\red{Ri}$．

输出格式

组队方式数模$\red{10^8}$取余的结果．

样例

输入样例

4 5
1
2
8
2

输出样例

3

提示

组队方式有$\red{(2，}$$\red{3)，}$$\red{(3，}$$\red{4)，}$$\red{(1，}$$\red{2，}$$\red{4)}$共三种