Mr. Furion is a math teacher. His students are very lazy and they do not like to do their homework. One day, Mr. Furion decides to give them a special problem in order to see whether his students are talents in math or they are just too lazy to do their homework. The problem is:
Given an integer k, n integers m
1,m
2…m
n, and a formula below:
X
1 xor X
2 xor X
3… xor X
n = k
Please figure out that how many integral solutions of the formula can satisfy:
0<=X
i<=m
i (i=1…n)
There are at most 100 test cases.
The first line of each test case contains two integers n and k. The second line of each test contains n integers: m
1,m
2…m
n. The meaning of n,k, m
1,m
2…m
n are described above. (1<=n<=50,0<=k,m
1,m
2…m
n<=2
^31-1 )
The input is ended by “0 0”.
You should output a integer for each test case, which is the number of solutions. As the number might be very large, you should only output the number modulo 1000000003.