#P2992. Pku3986 Math teacher's homework

    ID: 2114 传统题 1000ms 512MiB 尝试: 47 已通过: 21 难度: 7 上传者: 标签>CF2300提高+/省选-数位 DP计数 DP补集计数双射计数模逆元滚动数组

Pku3986 Math teacher's homework

题目描述

给出两个整数KK,nn 和一个整数序列M1,M2,…,MnM_1,M_2,\ldots,M_n,

求满足 X1⊕X2⊕⋯⊕Xn=KX_1\oplus X_2\oplus\cdots\oplus X_n=K,且对所有 1≤i≤n1\le i\le n 有 0≤Xi≤Mi0\le X_i\le M_i 的整数解的个数。其中 ⊕\oplus 表示按位异或。

输入格式

每个测试点包含至多 100100 组数据。每组数据的第一行包含两个整数 n,Kn,K,第二行包含 nn 个整数 M1,M2,…,MnM_1,M_2,\ldots,M_n。当 n=K=0n=K=0 时读入结束,这一行不属于测试数据。

1≤n≤501\le n\le50,0≤K,Mi≤231−10\le K,M_i\le2^{31}-1。

输出格式

每组输出一行,表示满足条件的解的个数对 109+310^9+3 取模的结果。

样例

输入

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

输出

1
0

UVa 1489 同题原件