spoj#TLE. Time Limit Exceeded

Time Limit Exceeded

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

  • 0 ≤ ai < 2M
  • ai is not divisible by ci (0 < ci ≤ 2M)
  • ai & ai+1 = 0 (that is, ai and ai+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 c1, ..., cN.

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.

time limit has been doubled, enjoy :D