39与93

题目限制

2000 ms 256 M

题目描述

$39$ 和 $93$ 两个人玩游戏，她们面前有 $n$ 堆石子，每堆石子数分别为 $b[1],b[2],...,b[n]$ ，石子一共有 $m$ 颗；每轮可以从一堆石子中拿走任意颗石子，但不能不拿。谁先不能操作，谁就输了。在游戏开始前， $93$ 可以扔掉 $x$ 堆石子，但是必须保证 $x$ 是 $s$ 的倍数 ，且 $x\le n-1$ 。 $39$ 先手，请问 $93$ 有多少种扔的方式，使得 $93$ 能够获胜。

输入格式

第一行包含两个正整数n,s(1≤n≤5e5,1≤s≤10)。 第二行包含n个正整数b[1],b[2],...,b[n] (1≤b[i]≤1e6)。 保证m≤1e7。

输出格式

输出一行一个整数，即方案数对1e9+7取模的结果。

数据范围

对于22%的数据，$1 \le n \le 30$；

对于38%的数据，$1 \le n \le 10000$；

对于100%的数据，$1 \le n \le 500000, 1 \le s \le 10, 1 \le b[i] \le 1000000, m \le 10000000$。

输入样例

5 2
1 3 4 1 2

输出样例

2