You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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$ 取模的结果。

5 2
1 3 4 1 2

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$。