题目描述

Farmer Han 开始玩飞盘之后，YDS 也打算让奶牛们享受飞盘的乐趣，他要组建一支奶牛飞盘队。

他的 $N$ 只奶牛，每只奶牛有一个飞盘水准指数 $R_i$ 。

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

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

输入格式

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

数据范围

$1 \le N \le 2000$

$1 \le R_i \le 100000$

$1 \le F \le 1000$

输出格式

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

数据样例

4 5 
1
2 
8 
2

3