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

[USACO09MAR] Cow Frisbee Team S

题目描述

给出 $n$ 个正整数 $a_i$，从中选出若干个（至少选一个），使得所选的数的和是 $K$ 的倍数。

求符合这个要求的选数方案数，输出答案对 $10^8$ 取模的值。

输入格式

第一行两个整数：$n \ K \ ( 1 \le n , K \le 2000 )$。

下来 $n$ 个整数 $a_i \ (1 \le a_i \le 10^5)$。

输出格式

一行一个整数，表示方案数对 $10^8$ 取模的值。

样例输入

4 5 
1 2 8 2

样例输出

3