P2946 [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