﻿ Fuzhou University OnlineJudge ﻿
Problem 2003 Math teacher's homework

## Problem Description

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 m1,m2…mn, and a formula below:

X1 xor X2 xor X3… xor Xn = k

Please figure out that how many integral solutions of the formula can satisfy:

0<=Xi<=mi (i=1…n)

## Input

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: m1,m2…mn. The meaning of n,k, m1,m2…mn are described above. (1<=n<=50,0<=k,m1,m2…mn<=2^31-1 )

The input is ended by “0 0”.

## Output

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.

## Sample Input

11 2047 1024 512 256 128 64 32 16 8 4 2 1 10 2047 1024 512 256 128 64 32 16 8 4 2 0 0

## Sample Output

1 0

Submit  Back  Status  Discuss
﻿