Winning Strategies in the Stone Game

Two players, A and B, play a game with stones. Initially, there are \(m\) stones which A has divided into \(n\) piles with sizes \(a_1,a_2,\dots,a_n\). The players take turns; in each move a player must choose one nonempty pile and remove any positive number of stones from it. The first player unable to make a move loses. Before the game begins, player B is allowed to discard (remove) several whole piles. However, the number of piles discarded must be a multiple of \(d\) and B is not allowed to discard all piles.

After B discards some piles, the remaining piles are used to play the game, with A moving first. Since this is essentially the classical Nim game, the winning condition is determined by the nim-sum (bitwise XOR) of the sizes of the remaining piles. If the nim-sum is \(0\) then the position is losing for the first mover (A), so B will win.

Your task is to count the number of ways B can discard piles so that:

• Not all piles are discarded (i.e. at least one pile remains).
• The number of discarded piles is a multiple of \(d\).
• If we define \(T\) as the set of remaining piles, then \(\bigoplus_{i \in T} a_i = 0\) (i.e. the nim-sum of the remaining piles is zero).
</p>

Note: It is equivalent to choose a nonempty subset \(T\) of piles such that \(|T| \equiv n \pmod{d}\) (because if \(T\) is the set of remaining piles then the number of discarded piles is \(n - |T|\), and \(n - |T|\) is a multiple of \(d\) if and only if \(|T| \equiv n \pmod{d}\)).

inputFormat

The input consists of two lines:

1. The first line contains two integers \(n\) and \(d\) where \(n\) is the number of piles and \(d\) is the required divisor for the number of piles discarded.
2. The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) representing the number of stones in each pile.

outputFormat

Output a single integer which is the number of ways for player B to discard some piles meeting the conditions so that the nim-sum of the remaining piles is zero.

sample

3 1
1 2 3

1

</p>