There are $n$ players playing a game. Every player has a skill value denoted by $S_i$. Before the game starts, each player can change their skill value to any non-negative integer smaller than their current skill value or leave it untouched. The coolness of the game is then defined as the bitwise-xor of the players skill values. We'd like to know for every number $X$ from $0$ to $m$ the number of ways that the coolness of the game equals $X$. Since these numbers may be extremely large, output them modulo $10^9 + 7$.

Input

The first line of input contains two integers $n$ and $m$, the number of the players and the parameter from the problem statement.
The second line of input contains $n$ space-separated integers, describing the skill values of the players.

$1 \le n, m, S_i \le 500$

Output

Output $m + 1$ integers, the i-th of which is the number of ways that the coolness of the game equals $i - 1$ modulo $10^9 + 7$.

Sample 2 Input

5 10
1 6 12 4 8
Sample 2 output

606 606 606 606 602 602 601 601 420 420 420