Winning Nim Distribution

Two players, C and W, are playing a two‐player impartial game. Initially, there are n identical stones. Player W first partitions these stones into m ordered piles. The i-th pile will have x_i stones such that:

• 0 \(\le x_i \le a_i\)
• \(x_1+x_2+\cdots+x_m=n\)

After the partition, the players take turns making moves, with player C starting. In each move, a player selects a non-empty pile and removes at least one stone from it. The player who is unable to make a move loses.

Using the theory of impartial games, it is known that player C can force a win if and only if the nim-sum of the pile sizes is nonzero. That is, if \[ x_1 \oplus x_2 \oplus \cdots \oplus x_m \neq 0, \] then player C has a winning strategy.

Your task is to count the number of ways to partition the stones (i.e. choose \(x_1,x_2,\dots,x_m\) satisfying the above conditions) such that player C is guaranteed to win.

inputFormat

The first line contains two integers n and m.

The second line contains m integers: \(a_1, a_2, \dots, a_m\).

outputFormat

Output a single integer representing the number of valid partitions in which player C can force a win.

sample

3 2
2 3

3