Given integers N (1 ≤ N ≤ 50) and M (1 ≤ M ≤ 15), compute the number of sequences a₁ ... a_N such that:

• 0 ≤ a_i < 2^M
• a_i is not divisible by c_i (0 < c_i ≤ 2^M)
• a_i & a_i+1 = 0 (that is, a_i and a_i+1 have no common bits in their binary representation)

Input

The first line contains the number of test cases, T (1 ≤ T ≤ 10). For each test case, the first line contains the integers N and M, and the second line contains the integers c₁ ... c_N.

Output

For each test case, output a single integer: the number of sequences described above, modulo 1,000,000,000.

Example

Input:
1
2 2
3 2

Output:
1

The only possible sequence is 2, 1.