Problem Description

Two players, A and B, play a game. There are $m$ stones in total. A splits them into $n$ piles, where the numbers of stones in each pile are $a_1,a_2,...,a_n$. In each round, a player may choose one pile and remove any positive number of stones from it, but they cannot remove zero stones. The first player who cannot make a move loses.

Before the game starts, B may discard some piles of stones, but B must ensure that the number of discarded piles is a multiple of $d$, and B cannot discard all stones.

A moves first. Ask how many ways B can discard piles such that B can win.

Input Format

The first line contains two positive integers $n,d$.

The second line contains $n$ positive integers $a_1,a_2,...,a_n$.

Output Format

Output one line with one integer, the number of valid ways modulo $10^9+7$.

5 2
1 3 4 1 2

2

Hint

For $100\%$ of the testdata, $1\le n\le 5\times 10^5$, $1\le d\le 10$, $1\le a_i\le 10^6$. $m$ is not given directly, but the testdata guarantees that $1\le m\le 10^7$.

Translated by ChatGPT 5