TLE - Time Limit Exceeded

no tags 

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


hide comments
airsplay: 2013-08-14 14:12:22

what the **** optimazation?

wzc1995: 2013-05-05 15:11:10

a little optimize is expected!!!!


Added by:Bin Jin
Date:2008-07-04
Time limit:0.192s-1.848s
Source limit:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: CPP
Resource:co-author: Neal Wu