该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

秋风拂过操场，银杏正黄。徐老师准备在班里举办一场“超级班级小队”评选： 他手里有一份名单，班里共有 $N$ 位同学，每位同学都有一个“魅力值” $C_i$（可以理解为才艺与人气的综合评分）。 评选规则很简单：从中挑若干人组成一个小队，小队的“总魅力”是入选同学魅力值之和。 而徐老师尤爱一个数字 $K$，他规定：小队的总魅力必须是 $K$ 的整数倍。

请你帮徐老师统计，有多少种不同的小队选择方案满足这一规定。由于结果可能很大，请输出答案对 $10^8$ 取模的值。

注：两种方案不同，指所选人的集合不同（与顺序无关）；至少选择 1 人，最多可选 $N$ 人。

输入格式

• 第 1 行：两个整数 $N$（人数）和 $K$（指定的数字）。
• 第 2 至 $N+1$ 行：第 $i$ 行给出一个整数 $C_i$，表示第 $i$ 位同学的魅力值。

输出格式

输出一个整数，表示满足条件的方案数（对 $10^8$ 取模）。

样例

输入

4 5
1
4
2
3

输出

3

数据范围

• $1 \le N \le 2000$
• $1 \le K \le 1000$
• $1 \le C_i \le 10^5$