You are given an array of length . Each element of the array is a non-negative integer less than . You have to partition it into two non-empty sub-sequences and such that each element belongs to exactly one of or . The score of such a partitioning is given by . Here, denotes the bitwise AND operation and denotes the bitwise OR operation.
For each between and , find the number of ways to partition the array such that the score is . Since this number can be large, you only need to find it modulo .
Two ways of partitioning are considered different if and only if there exists a pair of indices such that they are in the same part in one way, but in different parts in the other.
The first line contains two space separated integers, and .
The second line contains space-separated integers
Output space separated integers . where, is the number of ways, modulo , to partition such that the score is .
4 2 1 1 2 3
0 4 0 3
5 3 5 1 4 2 3
4 5 2 1 2 1 0 0
2 1 0 1