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.