题目描述

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

他要组建一只奶牛飞盘队

他的 $N$ 只奶牛，每只奶牛有一个飞盘水准指数 $R_i$．YDS 要选出 $1$ 只或多于 $1$ 只奶牛来参加他的飞盘队

由于 YDS 的幸运数字是 $F$，他希望所有奶牛的飞盘水准指数之和是幸运数字的倍数

帮 YDS 算算一共有多少种组队方式

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

输入格式

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

输出格式

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

4 5 
1
2 
8 
2

3

数据范围

$1 \le N \le 2000$

$1 \le R_i \le 100000$

$1 \le F \le 1000$