TLE  Time Limit Exceeded
Given integers N (1 ≤ N ≤ 50) and M (1 ≤ M ≤ 15), compute the number of sequences a_{1}, ..., 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_{1}, ..., 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.
time limit has been doubled, enjoy :D
hide comments
airsplay:
20130814 14:12:22
what the **** optimazation? 

wzc1995:
20130505 15:11:10
a little optimize is expected!!!! 
Added by:  Bin Jin 
Date:  20080704 
Time limit:  0.192s1.848s 
Source limit:  5000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: CPP 
Resource:  coauthor: Neal Wu 