题目描述

题目译自 XXIII Olimpiada Informatyczna — I etap Nim z utrudnieniem

Alicja 和 Bajtazar 最爱的消遣是玩 Nim 游戏。游戏需要若干堆筹码，分为多个堆。两人轮流操作，每次选择一堆，拿走任意正数个筹码。轮到谁时无筹码可拿，谁就输了。

Alicja 又邀 Bajtazar 来一局 Nim，但为了增加趣味，他们加了新规则。游戏有 $m$ 个筹码，Alicja 将其分为 $n$ 堆，堆大小为 $a_{1}, a_{2}, \ldots, a_{n}$。在游戏开始前，Bajtazar 可选择移除若干堆，但移除的堆数必须能被某固定数 $d$ 整除，且不能移除所有堆。移除的堆数可以为 $0$（即不移除任何堆）。之后，游戏按正常规则进行，由 Alicja 先手。

设 $k$ 为 Bajtazar 选择移除堆的方式数，使得无论 Alicja 如何操作，他都能赢。你的任务是计算 $k$ 对 $10^{9}+7$ 取模的结果。

输入格式

输入第一行包含两个正整数 $n$ 和 $d$，分别表示堆数和移除堆数的整除限制。

第二行包含 $n$ 个正整数 $a_{1}, a_{2}, \ldots, a_{n}$，表示每堆的筹码数。

输出格式

输出一行一个整数，表示 Bajtazar 能确保胜利的移除方式数，对 $10^{9}+7$ 取模。

5 2
1 3 4 1 2

2

字节扎尔可移除 $2$ 或 $4$ 堆，仅当移除大小为 $1$ 和 $4$ 的堆（有两种组合方式）时能确保胜利。

附加样例

1. $n=9, d=2$，结果为 $0$；
2. $n=12, d=4$；
3. $n=30, d=10$，每堆有 $30$ 个筹码；
4. $n=500000, d=2$，每堆有 $1$ 个筹码。

数据范围与提示

详细子任务附加限制及分值如下表所示。