3693：Math teacher's homework

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₁,m₂…m_n, and a formula below:

X₁ xor X₂ xor X₃… 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₁,m₂…m_n. The meaning of n,k, m₁,m₂…m_n are described above. (1<=n<=50,0<=k,m₁,m₂…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.