[POI2016] Nim z utrudnieniem
题目描述
A 和 B 两个人玩游戏,一共有 $m$ 颗石子,A 把它们分成了 $n$ 堆,每堆石子数分别为 $a_1,a_2,...,a_n$,每轮可以选择一堆石子,取掉任意颗石子,但不能不取。谁先不能操作,谁就输了。在游戏开始前,B 可以扔掉若干堆石子,但是必须保证扔掉的堆数是 $d$ 的倍数,且不能扔掉所有石子。
A 先手,请问 B 有多少种扔的方式,使得 B 能够获胜。
输入输出格式
输入格式
第一行包含两个正整数 $n,d$。
第二行包含 $n$ 个正整数 $a_1,a_2,...,a_n$。
输出格式
输出一行一个整数,即方案数对 $10^9+7$ 取模的结果。
输入输出样例
输入样例 #1
5 2
1 3 4 1 2
输出样例 #1
2
说明
对于 $100\%$ 的数据,$1\le n\le 5\times 10^5$,$1\le d\le 10$,$1\le a_i\le 10^6$,$m$ 不直接给出,但数据保证 $1\le m\le 10^7$。