Alice 和 Byteasar 最喜欢的消遣是玩 Nim 游戏。游戏开始时，筹码被任意分配到若干堆中。两名玩家轮流行动，每次行动可以选择任意一堆，并从中移除任意数量的筹码。无法进行行动的玩家输掉游戏。

Alice 刚刚提出了另一种 Nim 游戏。为了增加趣味性，他们决定稍微修改规则。Alice 像往常一样将 $m$ 个筹码分配到 $a_1, a_2, \dots, a_n$ 个堆中。然后，在游戏开始前，Byteasar 可以从游戏中移除一些堆。移除的堆的数量必须能被预先给定的数字 $d$ 整除，且至少要保留一堆。之后，他们进行常规的 Nim 游戏，由 Alice 先手。

令 $k$ 为 Byteasar 可以移除的合法堆子集数量，使得他在移除这些堆后，无论 Alice 如何行动，他都能赢得游戏。你的任务是求出 $k$ 除以 $10^9 + 7$ 的余数。

输入格式

输入的第一行包含两个正整数 $n$ 和 $d$，分别表示堆的数量以及 Byteasar 可以移除的堆数量的除数。

第二行描述这些堆：包含一个由 $n$ 个正整数 $a_1, a_2, \dots, a_n$ 组成的序列，其中 $a_i$ 表示第 $i$ 堆中筹码的数量。

输出格式

输出一行，包含一个整数：Byteasar 可以移除的、确保他后续获胜的不同堆子集的数量（对 $10^9 + 7$ 取模）。

样例

样例输入 1

5 2
1 3 4 1 2

样例输出 1

2

说明

Byteasar 可以移除 2 堆或 4 堆。他只有在移除一堆包含 1 个筹码的堆和一堆包含 4 个筹码的堆时才能获胜；共有两组满足此条件的堆。

子任务

测试集由以下子任务组成。在所有子任务中，满足 $n \le 500\,000$，$d \le 10$，$a_i \le 1\,000\,000$。此外，筹码总数 $m = a_1 + a_2 + \dots + a_n$ 不超过 $10\,000\,000$。注意内存限制在不同子任务中有所不同。