题目描述

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

他的 $n$ 只奶牛，每只部有一个飞盘水准指数 $r_i$。约翰要选出一只或多于一只奶牛来参加他的飞盘队。

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

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

输入格式

第一行输入 $n$ 和 $f$，之后 $n$ 行输入 $r_i$。

输出格式

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

4 5
1
2
8
2

3

提示

组队方式有 $(2,3),(3,4),(1,2,4)$ 共三种。

题目来源

Silver

数据规模与约定

对于 $100 \%$ 的数据 $1 \le n \le 2000$，$1 \le r_i \le 100000$，$1 \le f \le 1000$。