Problem:


					Max Score: $400$ Points
					

Problem Statement

Sample testcase 3 has a mistake, so we erased this case and rejudged all solutions of this problem. (21:01)

						Snuke got a sequence $a$ of length $n$ from AtCoder company. All elements in $a$ are distinct.

						He made a sequence $b$, but actually, he is not remembered it. 

						However, he is remembered a few things about sequence $b$. 

All elements in $b$ are distinct. 

All elements in $b$ is in $a$.

$b_1 \oplus b_2 \oplus \cdots \oplus b_r = k$. ($r$ is length of sequence $b$) [$\oplus$ means XOR]

						For example, if $a = { 1, 2, 3 }$ and $k = 1$, he can make $b = { 1 }, { 2, 3 }, { 3, 2 }$. 

						He wants to restore sequence $b$, but he says that there are too many ways and he can't restore it.
						Please calculate the ways to make $b$ and help him. 

						Since the answer can be large, print the answer modulo $1,000,000,007$. 

Input

						The input is given from Standard Input in the following format:

$n \ k$
$a_1 \ a_2 \ \cdots \ a_n$

Output

Print the number of ways to make sequence $b$. 

Print the answer modulo $1,000,000,007$. 

Constraints

$1 \le n \le 100$

$1 \le a_i, k \le 255$

$i \neq j \Rightarrow a_i \neq a_j$

Subtasks

						Subtask 1 [ $50$ points ] 

$1 \le n \le 4$

						Subtask 2 [ $170$ points ] 

$1 \le n \le 20$

						Subtask 3 [ $180$ points ] 

There are no additional constraints.

Sample Input 1

3 1
1 2 3

Sample Output 1

3

					You can make 3 patterns: $b = \{ 1 \}, \{ 2, 3 \}, \{ 3, 2 \}$

Sample Input 2

3 10
8 7 5

Sample Output 2

6

					You can make 6 patterns: $b = \{ 5, 7, 8 \}, \{ 5, 8, 7 \}, \{ 7, 5, 8 \}, \{ 7, 8, 5 \}, \{ 8, 5, 7 \}, \{ 8, 7, 5 \}$.

Sample Input 4

25 127
5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125

Sample Output 4

235924722

Please output answer mod $1,000,000,007$.

				writer: E869120 



Sample input:
3 1
1 2 3


Sample output:
3

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・項数、和 -> 通り数 を持ってdp
"""

import numpy as np

N,K,*A = map(int,read().split())

MOD = 10**9 + 7

dp = np.zeros((N+1,256),np.int64)
dp[0,0] = 1
for x in A:
    dp[1:,np.arange(256)^x] += dp[:-1]

fact = np.ones(N+1,np.int64)
for n in range(1,N+1):
    fact[n] = fact[n-1] * n % MOD

answer = (fact * dp[:,K] % MOD).sum() % MOD
print(answer)

Submission status: Wrong Answer

Solution code:
M=10e9+7
o=lambda:map(int,raw_input().split())
n,k=o()
a=o()
dp=[[0]*256 for _ in [0]*(n+1)]
dp[0][0]=1
for i in range(n):
    _dp=dp
    for l in reversed(range(1,i+2)):
        for j in range(256):_dp[l][j]+=dp[l-1][a[i]^j]
    dp=_dp
p=[1]*(n+1)
for i in range(n):p[i+1]=p[i]*(i+1)%M
print sum([dp[l][k]*p[l] for l in range(1,n+1)])%M

Submission status: Wrong Answer

Solution code:
M=1000000007
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
dp=[[0]*256 for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    _dp=dp
    for l in reversed(range(1,i+2)):
        for j in range(256):
            _dp[l][j]+=dp[l-1][a[i]^j]
    dp=_dp
    print dp[2][:5]
p=[1]*(n+1)
for i in range(1,n+1):
    p[i]=p[i-1]*i%M
print sum([dp[l][k]*p[l] for l in range(1,n+1)])%M

Submission status: Wrong Answer

Solution code:
M=1000000007
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
dp=[[0]*256 for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    _dp=dp
    for j in range(256):
        for l in range(n+1):
            if l>0:_dp[l][j]+=dp[l-1][j^a[i]]
    dp=_dp
p=[1]*(n+1)
for i in range(1,n+1):
    p[i]=p[i-1]*i%M
print sum([dp[l][k]*p[l] for l in range(1,n+1)])%M

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
mod = 10**9 + 7
a = list(map(int, input().split()))
dp = [[[0]*256 for _ in range(n+1)]for i in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
  x = a[i]
  dp[i+1][0] = dp[i][0][:]
  for j in range(n):
    for k in range(256):
      dp[i+1][j+1][k] = (dp[i][j+1][k] + dp[i][j][k^x])%mod
f = 1
ans = 0
for j in range(1,n+1):
  f = f*j%mod
  ans += dp[n][j][m]*f
  ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())

MOD = 10**9 + 7

C = {a for a in A}
n = len(C)
m = [[0]*256 for i in range(n+1)]
m[0][0] = 1
for c in C:
    for i in range(n-1, -1, -1):
        for j in range(256):
            m[i+1][c^j] += m[i][j]
            m[i+1][c^j] %= MOD

ans = 0
r = 1
for i in range(1, n+1):
    r = (r * i) % MOD
    ans += r * m[i][k]
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
dp=[[[0]*(1<<8) for _ in xrange(n+1)] for _ in xrange(n+1)]
for i in xrange(n):
    dp[i+1][1][a[i]]=1
for i in xrange(n):
    for j in xrange(n):
        for l in xrange(1<<8):
            dp[i+1][j+1][a[i]^l]+=(j+1)*dp[i][j][l]%mod
            dp[i+1][j][l]+=dp[i][j][l]%mod
ans=0
for j in xrange(1,n+1):
    ans=(ans+dp[n][j][k])%mod
print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n,x=map(int,input().split())
a=list(map(int,input().split()))
dp=[[[0]*256 for j in range(n+1)] for k in range(2)]
dp[0][0][0]=1
for i in range(n):
  for j in range(n+1):
    for k in range(256):
      dp[(i+1)&1][j][k]=dp[i&1][j][k]
  for j in range(n):
    for k in range(256):
      dp[(i+1)&1][j+1][k^a[i]]+=dp[i&1][j][k]
      if mod<=dp[(i+1)&1][j][k^a[i]]:
        dp[(i+1)&1][j][k^a[i]]-=mod

ans=0
fac=[1]*(n+1)
for i in range(1,n+1):
  fac[i]=fac[i-1]*i
  if mod<=fac[i]:
    fac[i]-=mod
for j in range(n+1):
  ans+=dp[n&1][j][x]*fac[j]
  ans%=mod

print(ans)

Submission status: Accepted

Solution code:

n,K=map(int,input().split())
lists=list(map(int,input().split()))
mod=10**9+7
dp=[[["inf" for i in range(256)] for j in range(n+1)] for k in range(n+1)]
#dp[i][j][k]=カードのi番目までからjこまでを取ってxorの値をkにする方法
#dp[i][j]=="inf" (i<jの時)
for i in range(n+1):
    dp[i][0][0]=1
for i in range(1,n+1):
    num=lists[i-1]
    for j in range(1,i+1):
        for k in range(256):
            if dp[i-1][j-1][k^num]!="inf" or dp[i-1][j][k]!="inf": 
                s=0
                if dp[i-1][j][k]!="inf":
                    s+=dp[i-1][j][k]
                if dp[i-1][j-1][k^num]!="inf":
                    s+=dp[i-1][j-1][k^num]
                dp[i][j][k]=s%mod
            else:
                pass
ans=0
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
A=find_power(100,mod)

for i in range(n+1):
    if dp[n][i][K]!="inf":
        ans+=dp[n][i][K]*A[i]
        ans=ans%mod
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
mod = 10**9 + 7
a = list(map(int, input().split()))
dp = [[[0]*256 for _ in range(n+1)]for i in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
  x = a[i]
  dp[i+1][0] = dp[i][0][:]
  for j in range(n):
    for k in range(256):
      dp[i+1][j+1][k] = (dp[i][j+1][k] + dp[i][j][k^x])%mod
f = 1
ans = 0
for j in range(1,n+1):
  f = f*j%mod
  ans += dp[n][j][m]*f
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・項数、和 -> 通り数 を持ってdp
"""

import numpy as np

N,K,*A = map(int,read().split())

MOD = 10**9 + 7

dp = np.zeros((N+1,256),np.int64)
dp[0,0] = 1
for x in A:
    dp[1:,np.arange(256)^x] += dp[:-1]
    dp %= MOD

fact = np.ones(N+1,np.int64)
for n in range(1,N+1):
    fact[n] = fact[n-1] * n % MOD

answer = (fact * dp[:,K] % MOD).sum() % MOD
print(answer)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
dp = [[[0]*(n+1) for i in range(256)] for i in range(n+1)]
dp[1][a[0]][1],x,mod,ans = 1,[0,1],10**9+7,0
for i in range(n+1): dp[i][0][0] = 1
for i in range(2,n+1):
	for j in range(256):
		for k in range(1,i+1): dp[i][j][k] = dp[i-1][j^a[i-1]][k-1]+dp[i-1][j][k]
for i in range(2,257): x.append((x[-1]*i)%mod)
for i in range(n+1): ans = (ans+dp[-1][m][i]*x[i])%mod
print(ans)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())

MOD = 10**9 + 7

C = {a for a in A}
n = len(C)
m = [[0]*256 for i in range(n+1)]
m[0][0] = 1
for c in C:
    for i in range(n-1, -1, -1):
        s = m[i]; t = m[i+1]
        for j in range(256):
            t[c^j] += s[j]

ans = 0
r = 1
for i in range(1, n+1):
    r = (r * i) % MOD
    ans += r * m[i][k]
    ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
src = list(map(int,input().split()))
MOD = 10**9+7

dp = [[0 for k in range(256)] for i in range(N+1)]
dp[0][0] = 1
for i,a in enumerate(src):
    for j in range(i,-1,-1):
        for k in range(256):
            if dp[j][k] == 0: continue
            dp[j+1][k^a] += dp[j][k]

ans = 0
fact = 1
for i in range(1,N+1):
    ans += (dp[i][K] * fact) % MOD
    fact = (fact * (i+1)) % MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
M=10**9+7
o=lambda:map(int,raw_input().split())
n,k=o()
a=o()
dp=[[0]*256 for _ in [0]*(n+1)]
dp[0][0]=1
for i in range(n):
    _dp=dp
    for l in reversed(range(1,i+2)):
        for j in range(256):_dp[l][j]+=dp[l-1][a[i]^j]
    dp=_dp
p=[1]*(n+1)
for i in range(n):p[i+1]=p[i]*(i+1)%M
print sum([dp[l][k]*p[l] for l in range(1,n+1)])%M

Submission status: Accepted

Solution code:
M=1000000007
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
dp=[[0]*256 for _ in range(n+1)]
dp[0][0]=1
for i in range(n):
    _dp=dp
    for l in reversed(range(1,i+2)):
        for j in range(256):
            _dp[l][j]+=dp[l-1][a[i]^j]
    dp=_dp
p=[1]*(n+1)
for i in range(1,n+1):
    p[i]=p[i-1]*i%M
print sum([dp[l][k]*p[l] for l in range(1,n+1)])%M

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
a = map(int, raw_input().split())
dp = [0] * 256 * 101
dp[0] = 1
for i, x in enumerate(a):
    ndp = dp[:]
    for j in xrange(256):
        for k in xrange(i + 1):
            ndp[(j^x)+k*256+256] += dp[j+k*256]
            if ndp[(j^x)+k*256+256] >= 1000000007:
                ndp[(j^x)+k*256+256] -= 1000000007
    dp = ndp
ans = 0
s = 1
for i in xrange(1, n + 1):
    s = s * i % 1000000007
    ans += dp[m+i*256] * s % 1000000007
print ans % 1000000007

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy3

import functools
import itertools
import math
import operator


P = 1000000007


def xors(seq):
    return functools.reduce(operator.xor, seq)


def solve(n, k, xs):
    l = len(xs)
    a = 0
    for i in range(1, l + 1):
        for ys in itertools.combinations(xs, i):
            if xors(ys) == k:
                a += math.factorial(i)
                a %= P
    return a


def main():
    n, k = map(int, input().split())
    assert n <= 20
    xs = [int(x) for x in input().split()]
    print(solve(n, k, xs))


if __name__ == '__main__':
    main()