[POI2016]Nim z utrudnieniem

时间限制:30s      空间限制:64MB

题目描述

A和B两个人玩游戏,一共有m颗石子,A把它们分成了n堆,每堆石子数分别为a[1],a[2],...,a[n],每轮可以选择一堆石子,取掉任意颗石子,但不能不取。谁先不能操作,谁就输了。在游戏开始前,B可以扔掉若干堆石子,但是必须保证扔掉的堆数是d的倍数,且不能扔掉所有石子。A先手,请问B有多少种扔的方式,使得B能够获胜。


输入格式

第一行包含两个正整数n,d(1<=n<=500000,1<=d<=10)。
第二行包含n个正整数a[1],a[2],...,a[n](1<=a[i]<=1000000)。
本题中m不直接给出,但是保证m<=10000000。


输出格式

输出一行一个整数,即方案数对10^9+7取模的结果。


样例输入

5 2
1 3 4 1 2

样例输出

2

提示

没有写明提示


题目来源

鸣谢Claris