Given an array arr of N integers and an integer K, find the number of subsets of arr having XOR of elements as K.
 
Example 1:
Input:
N = 4
k = 6
arr: 6 9 4 2
Output:
2
Explanation:
The subsets are 
{4,2} and {6}
Example 2:
Input:
N = 5
K = 4
arr: 1 2 3 4 5
Output:
4
Explanation:
The subsets are {1, 5},
{4}, {1, 2, 3, 4},
and {2, 3, 5}
Your Task:
You don't need to read input or print anything. Your task is to complete the function subsetXOR() which takes the array arr[], its size N, and an integer K as input parameters and returns the number of subsets having xor as K
 
Expected Time Complexity: O(N*M)
Expected Space Complexity: O(N*M)
Note: M = maximum value any XOR subset will acquire
 
Constraints:
1<=N<=20
1<=K<=100
0<=arr[i]<=100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Bit manipulation

Data structures

Starter code: #User function Template for python3



import math

class Solution:

    def subsetXOR(self, arr, N, K): 

        # code here

Solutions:
import math

class Solution:

	def subsetXOR(self, arr, N, k):
		dp = [[0 for i in range(128)] for j in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(128):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]]
		return dp[N][k]


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		m = arr[0]
		for i in range(1, N):
			if arr[i] > m:
				m = arr[i]
		M = 2 ** (int(math.log2(m)) + 1) - 1
		if K > M:
			return 0
		dp = [[0] * (M + 1) for _ in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(M + 1):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]]
		return dp[N][K]


import math

class Solution:
	dp = []

	def rec(self, i, x, k, arr, n):
		if i == n:
			if x == k:
				return 1
			else:
				return 0
		ans = 0
		if self.dp[i][x] != -1:
			return self.dp[i][x]
		a1 = self.rec(i + 1, x ^ arr[i], k, arr, n)
		a2 = self.rec(i + 1, x, k, arr, n)
		ans = a1 + a2
		self.dp[i][x] = ans
		return ans

	def subsetXOR(self, arr, N, K):
		self.dp = []
		for i in range(len(arr)):
			b = []
			for j in range(9999):
				b.append(-1)
			self.dp.append(b)
		return self.rec(0, 0, K, arr, N)


import math
from functools import lru_cache

class Solution:

	def subsetXOR(self, arr, N, K):

		@lru_cache(maxsize=None)
		def helper(curr_idx, xor, target):
			cnt = 0
			if curr_idx == N:
				if xor == target:
					return 1
					cnt += 1
				else:
					return 0
			left = 0
			right = 0
			for i in range(curr_idx, N):
				if left == 0:
					cnt += helper(i + 1, xor ^ arr[i], target)
					left = 1
				if right == 0:
					cnt += helper(i + 1, xor, target)
					right = 1
			return cnt
		return helper(0, 0, K)


import math

class Solution:
	dp = []

	def gen(self, arr, n, k, sor):
		if n < 0:
			if sor == k:
				return 1
			return 0
		if self.dp[n][sor] != -1:
			return self.dp[n][sor]
		l = self.gen(arr, n - 1, k, sor ^ arr[n])
		r = self.gen(arr, n - 1, k, sor)
		self.dp[n][sor] = l + r
		return l + r

	def subsetXOR(self, arr, N, K):
		self.dp = []
		for i in range(len(arr)):
			b = []
			for j in range(9999):
				b.append(-1)
			self.dp.append(b)
		return self.gen(arr, N - 1, K, 0)


class Solution:

	def solve(self, arr, i, k, curr, dp):
		if i == 0:
			return curr == k
		if dp[i][curr] != -1:
			return dp[i][curr]
		taken = self.solve(arr, i - 1, k, curr ^ arr[i - 1], dp)
		nottake = self.solve(arr, i - 1, k, curr, dp)
		dp[i][curr] = taken + nottake
		return dp[i][curr]

	def subsetXOR(self, arr, N, K):
		dp = [[-1] * 201 for i in range(N + 1)]
		return self.solve(arr, N, K, 0, dp)


from collections import defaultdict
from typing import List

class Solution:

	def generate(self, arr: List[int], curr: int, n: int, XOR: defaultdict, number: int) -> None:
		if curr == n:
			XOR[number] += 1
			return
		self.generate(arr, curr + 1, n, XOR, number ^ arr[curr])
		self.generate(arr, curr + 1, n, XOR, number)

	def subsetXOR(self, arr: List[int], N: int, K: int) -> int:
		P1 = defaultdict(int)
		P2 = defaultdict(int)
		self.generate(arr, 0, N // 2, P1, 0)
		self.generate(arr, N // 2, N, P2, 0)
		res = 0
		for x in P1:
			find = K ^ x
			res += P2[find] * P1[x]
		return res


import math

class Solution:

	def subsetXOR(self, arr, N, K):

		def recurse(idx, xor):
			if idx == 0:
				return xor == K
			if (idx, xor) in dp:
				return dp[idx, xor]
			dp[idx, xor] = recurse(idx - 1, xor ^ arr[idx - 1]) + recurse(idx - 1, xor)
			return dp[idx, xor]
		dp = {}
		return recurse(N, 0)


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		dp = {0: 1}
		ans = 0
		for x in arr[:N]:
			key = x ^ K
			if key in dp:
				ans += dp[key]
			for (key, value) in list(dp.items()):
				xor = x ^ key
				dp[xor] = dp.get(xor, 0) + value
		return ans


import math

class Solution:

	def subsetXOR(self, arr, n, k):
		max_ele = arr[0]
		for i in range(1, n):
			if arr[i] > max_ele:
				max_ele = arr[i]
		m = (1 << int(math.log2(max_ele) + 1)) - 1
		if k > m:
			return 0
		dp = [[0 for i in range(m + 1)] for i in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(m + 1):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]]
		return dp[n][k]


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		dp = [[-1 for i in range(300)] for i in range(N + 1)]

		def recursive(N, cur=0):
			nonlocal arr, dp, K
			if N == 0:
				if cur == K:
					return 1
				else:
					return 0
			if dp[N][cur] != -1:
				return dp[N][cur]
			op1 = recursive(N - 1, cur)
			temp = cur ^ arr[N - 1]
			op2 = recursive(N - 1, temp)
			dp[N][cur] = op1 + op2
			return dp[N][cur]
		a = recursive(N)
		return a


from collections import defaultdict
import math

class Solution:

	def dfs(self, index, x, N):
		if index >= N:
			if x == Solution.target:
				return 1
			return 0
		if (index, x) in Solution.mem:
			return Solution.mem[index, x]
		a = self.dfs(index + 1, x ^ Solution.arr[index], N)
		b = self.dfs(index + 1, x, N)
		Solution.mem[index, x] = a + b
		return a + b

	def subsetXOR(self, arr, N, target):
		Solution.arr = arr
		Solution.mem = {}
		Solution.target = target
		return self.dfs(0, 0, N)


import math

class Solution:

	def subsetXOR(self, arr, n, k):
		memo = dict()

		def f(ind, xor):
			if ind == n:
				if xor == k:
					return 1
				return 0
			if (ind, xor) in memo:
				return memo[ind, xor]
			nt = f(ind + 1, xor)
			t = f(ind + 1, xor ^ arr[ind])
			memo[ind, xor] = t + nt
			return nt + t
		return f(0, 0)


import math

class Solution:

	def rec(self, i, x, arr, N, K):
		if i == N:
			if x == K:
				return 1
			else:
				return 0
		ans = 0
		if dp[i][x] != -1:
			return dp[i][x]
		a1 = Solution.rec(self, i + 1, x ^ arr[i], arr, N, K)
		a2 = Solution.rec(self, i + 1, x, arr, N, K)
		ans = a1 + a2
		dp[i][x] = ans
		return ans

	def subsetXOR(self, arr, N, K):
		global dp
		dp = [[-1 for i in range(200)] for j in range(20)]
		return Solution.rec(self, 0, 0, arr, N, K)


import math

class Solution:

	def helper(self, arr, n, k, dp):
		if n == 0:
			return k == 0
		if dp[n][k] != -1:
			return dp[n][k]
		pick = self.helper(arr, n - 1, k ^ arr[n - 1], dp)
		notPick = self.helper(arr, n - 1, k, dp)
		dp[n][k] = pick + notPick
		return dp[n][k]

	def subsetXOR(self, arr, N, K):
		dp = [[-1 for i in range(129)] for j in range(N + 1)]
		return self.helper(arr, N, K, dp)


class Solution:

	def solve(self, arr, n, k, i, xor):
		if i == n:
			return 1 if xor == k else 0
		if dp[i][xor] != -1:
			return dp[i][xor]
		x = self.solve(arr, n, k, i + 1, arr[i] ^ xor)
		y = self.solve(arr, n, k, i + 1, xor)
		dp[i][xor] = x + y
		return dp[i][xor]

	def subsetXOR(self, arr, n, k):
		global dp
		dp = [[-1 for i in range(200)] for j in range(25)]
		return self.solve(arr, n, k, 0, 0)


import math

class Solution:

	def esubsetXOR(self, arr, n, k):
		d = {}
		xor = 0
		count = 0
		for i in arr:
			xor = xor ^ i
			if xor not in d:
				d[xor] = 0
			d[xor] += 1
			count += 1 if xor == k else 0
			if xor != k:
				count += d.get(k ^ xor, 0)
		return count

	def subsetXOR(self, arr, n, k):
		max_ele = arr[0]
		for i in range(1, n):
			if arr[i] > max_ele:
				max_ele = arr[i]
		m = (1 << int(math.log2(max_ele) + 1)) - 1
		if k > m:
			return 0
		dp = [[0 for i in range(m + 1)] for i in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(m + 1):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]]
		return dp[n][k]


class Solution:

	def helper(self, n, xor, k, arr, dp):
		if n == 0:
			if xor == k:
				return 1
			else:
				return 0
		if dp[n][xor] != -1:
			return dp[n][xor]
		pick = self.helper(n - 1, xor ^ arr[n - 1], k, arr, dp)
		notpick = self.helper(n - 1, xor, k, arr, dp)
		dp[n][xor] = pick + notpick
		return pick + notpick

	def subsetXOR(self, arr, N, K):
		dp = [[-1 for i in range(130)] for j in range(N + 1)]
		return self.helper(N, 0, K, arr, dp)


import math

class Solution:

	def helper(self, n, k, arr, dp):
		if n == 0:
			if k == 0:
				return 1
			else:
				return 0
		if dp[n][k] != -1:
			return dp[n][k]
		pick = self.helper(n - 1, k ^ arr[n - 1], arr, dp)
		notpick = self.helper(n - 1, k, arr, dp)
		dp[n][k] = pick + notpick
		return pick + notpick

	def subsetXOR(self, arr, N, K):
		dp = [[-1 for i in range(10001)] for j in range(N + 1)]
		return self.helper(N, K, arr, dp)


import math

class Solution:

	def xor(self, arr, index, length, xor, key, dpArr):
		if index == length:
			if xor == key:
				return 1
			return 0
		if dpArr[index][xor] != -1:
			return dpArr[index][xor]
		a1 = self.xor(arr, index + 1, length, xor ^ arr[index], key, dpArr)
		a2 = self.xor(arr, index + 1, length, xor, key, dpArr)
		dpArr[index][xor] = a1 + a2
		return a1 + a2

	def subsetXOR(self, arr, length, key):
		dpArr = [[-1] * 200 for i in range(0, 25)]
		return self.xor(arr, 0, length, 0, key, dpArr)


class Solution:

	def subsetXOR(self, arr, N, K):
		double_penetration = [[0 for i in range(128)] for j in range(N + 1)]
		double_penetration[0][0] = 1
		for i in range(1, N + 1):
			for j in range(128):
				double_penetration[i][j] = double_penetration[i - 1][j] + double_penetration[i - 1][j ^ arr[i - 1]]
		return double_penetration[N][K]


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		max_ele = arr[0]
		for i in range(1, N):
			if arr[i] > max_ele:
				max_ele = arr[i]
		m = (1 << int(math.log2(max_ele) + 1)) - 1
		if K > m:
			return 0
		dp = [[0 for j in range(m + 1)] for i in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(m + 1):
				xr = arr[i - 1] ^ j
				dp[i][xr] = dp[i - 1][j] + dp[i - 1][xr]
		return dp[N][K]


import math

class Solution:

	def subsetXOR(self, arr, N, K):

		def recur(arr, N, K, xr, ind, D):
			if ind == N:
				if xr == K:
					return 1
				return 0
			if (xr, ind) in D:
				return D[xr, ind]
			x = recur(arr, N, K, xr ^ arr[ind], ind + 1, D)
			y = recur(arr, N, K, xr, ind + 1, D)
			D[xr, ind] = x + y
			return D[xr, ind]
		return recur(arr, N, K, 0, 0, dict())


import math
from functools import lru_cache

class Solution:

	def subsetXOR(self, arr, N, K):

		@lru_cache(None)
		def recur(index, xor):
			if index == N:
				return xor == K
			left = recur(index + 1, xor ^ arr[index])
			right = recur(index + 1, xor)
			return left + right
		return recur(0, 0)


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		dp = {}

		def recur(index, xor):
			if index == N:
				return xor == K
			if (index, xor) in dp:
				return dp[index, xor]
			left = recur(index + 1, xor ^ arr[index])
			right = recur(index + 1, xor)
			dp[index, xor] = left + right
			return left + right
		return recur(0, 0)


import math

class Solution:

	def solve(self, arr, N, K, idx, xor, dp):
		if idx == N:
			if xor == K:
				return 1
			return 0
		if dp[idx][xor] != -1:
			return dp[idx][xor]
		Take = self.solve(arr, N, K, idx + 1, xor ^ arr[idx], dp)
		NotTake = self.solve(arr, N, K, idx + 1, xor, dp)
		dp[idx][xor] = Take + NotTake
		return dp[idx][xor]

	def subsetXOR(self, arr, N, K):
		dp = [[-1 for i in range(128)] for j in range(N)]
		return self.solve(arr, N, K, 0, 0, dp)


import math

class Solution:

	def subsetXOR(self, arr, N, K):

		def helper(i, n, k, arr, x):
			if i == n:
				return x == k
			if dp[i][x] != -1:
				return dp[i][x]
			take = helper(i + 1, n, k, arr, x ^ arr[i])
			nonTake = helper(i + 1, n, k, arr, x)
			dp[i][x] = take + nonTake
			return dp[i][x]
		dp = [[-1 for _ in range(201)] for _ in range(21)]
		return helper(0, N, K, arr, 0)


import sys
sys.setrecursionlimit(int(1000000.0))
import math

class Solution:

	def subsetXOR(self, A, N, K):
		mx = A[0]
		for i in range(1, N):
			if A[i] > mx:
				mx = A[i]
		mx = (1 << int(math.log2(mx) + 1)) - 1
		if K > mx:
			return 0
		dp = [[0 for i in range(mx + 1)] for i in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(mx + 1):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ A[i - 1]]
		return dp[-1][K]


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		memo = {}

		def func(i, xor, arr, memo, K, N):
			if i == N:
				if xor == K:
					return 1
				return 0
			if (i, xor) not in memo:
				take = func(i + 1, xor ^ arr[i], arr, memo, K, N)
				nottake = func(i + 1, xor, arr, memo, K, N)
				memo[i, xor] = take + nottake
			return memo[i, xor]
		return func(0, 0, arr, memo, K, N)


import math

class Solution:

	def f(self, i, xor, k, arr, memo, n):
		if i == n:
			if xor == k:
				return 1
			return 0
		if (i, xor) not in memo:
			take = self.f(i + 1, xor ^ arr[i], k, arr, memo, n)
			nottake = self.f(i + 1, xor, k, arr, memo, n)
			memo[i, xor] = take + nottake
		return memo[i, xor]

	def subsetXOR(self, arr, N, K):
		memo = {}
		return self.f(0, 0, K, arr, memo, N)


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		dp = [[-1 for i in range(128)] for j in range(N + 1)]
		ans = self.solve(arr, N, K, dp)
		return ans

	def solve(self, arr, n, k, dp):
		if n == 0:
			if k == 0:
				return 1
			else:
				return 0
		if dp[n][k] != -1:
			return dp[n][k]
		tk = self.solve(arr, n - 1, arr[n - 1] ^ k, dp)
		nt = self.solve(arr, n - 1, k, dp)
		dp[n][k] = tk + nt
		return dp[n][k]

	def solve1(self, arr, n, k):
		dp = [[0 for i in range(128)] for j in range(n + 1)]
		dp[0][0] = 1
		for i in range(1, n + 1):
			for j in range(128):
				dp[i][j] = dp[i - 1][j ^ arr[i - 1]] + dp[i - 1][j]
		return dp[n][k]


import math

class Solution:

	def subsetXOR(self, arr, n, k):
		xorSet = {0: 1}
		res = 0
		for x in arr[:n]:
			key = x ^ k
			if key in xorSet:
				res += xorSet[key]
			for (key, val) in list(xorSet.items()):
				xor = x ^ key
				xorSet[xor] = xorSet.get(xor, 0) + val
		return res


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		dp = [[-1 for j in range(200)] for i in range(25)]

		def helper(ind, xor, k, arr, n):
			if ind == n:
				if xor == k:
					return 1
				return 0
			if dp[ind][xor] != -1:
				return dp[ind][xor]
			sol = 0
			take = helper(ind + 1, xor ^ arr[ind], k, arr, n)
			ignore = helper(ind + 1, xor, k, arr, n)
			res = take + ignore
			dp[ind][xor] = res
			return res
		ans = helper(0, 0, K, arr, N)
		return ans


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		rak = [[0 for i in range(128)] for j in range(N + 1)]
		rak[0][0] = 1
		for i in range(1, N + 1):
			for j in range(128):
				rak[i][j] = rak[i - 1][j] + rak[i - 1][j ^ arr[i - 1]]
		return rak[N][K]
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = input().split()
		N = int(N)
		K = int(K)
		arr = input().split(' ')
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.subsetXOR(arr, N, K))


import math

class Solution:

	def subsetXOR(self, arr, N, K):

		def func(N, K):
			if N == 0:
				return K == 0
			if dp[N][K] != -1:
				return dp[N][K]
			take = func(N - 1, K ^ arr[N - 1])
			leav = func(N - 1, K)
			dp[N][K] = take + leav
			return dp[N][K]
		dp = [[-1] * 128 for _ in range(N + 1)]
		return func(N, K)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = input().split()
		N = int(N)
		K = int(K)
		arr = input().split(' ')
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.subsetXOR(arr, N, K))


from functools import lru_cache
import math

class Solution:

	def subsetXOR(self, arr, N, K):

		@lru_cache(None)
		def func(N, K):
			if N == 0:
				return K == 0
			take = func(N - 1, K ^ arr[N - 1])
			leav = func(N - 1, K)
			return take + leav
		return func(N, K)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = input().split()
		N = int(N)
		K = int(K)
		arr = input().split(' ')
		for itr in range(N):
			arr[itr] = int(arr[itr])
		ob = Solution()
		print(ob.subsetXOR(arr, N, K))


class Solution:

	def subsetXOR(self, arr, N, K):
		ht = {0: 1}
		cnt = 0
		for i in arr[:N]:
			temp = i ^ K
			if temp in ht:
				cnt += ht[temp]
			for (k, v) in list(ht.items()):
				xor = i ^ k
				ht[xor] = ht.get(xor, 0) + v
		return cnt


def func(arr, si, k, curr, memo):
	if si == len(arr):
		if curr == k:
			return 1
		return 0
	if memo[si][curr] != -1:
		return memo[si][curr]
	memo[si][curr] = func(arr, si + 1, k, curr ^ arr[si], memo) + func(arr, si + 1, k, curr, memo)
	return memo[si][curr]
import math

class Solution:

	def subsetXOR(self, arr, N, k):
		max_ele = arr[0]
		for i in range(1, N):
			if arr[i] > max_ele:
				max_ele = arr[i]
		m = (1 << int(math.log2(max_ele) + 1)) - 1
		if k > m:
			return 0
		dp = [[0 for i in range(m + 1)] for i in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(m + 1):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]]
		return dp[N][k]


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		l = []
		for i in arr:
			try:
				l.append(int(i))
			except:
				continue
		arr = l
		m = max(arr)
		c = 0
		while m > 0:
			m = m // 2
			c += 1
		s = pow(2, c) - 1
		if K > s:
			return 0
		dp = [[0 for i in range(s + 1)] for j in range(N + 1)]
		dp[0][0] = 1
		for i in range(1, N + 1):
			for j in range(s + 1):
				dp[i][j] = dp[i - 1][j] + dp[i - 1][j ^ arr[i - 1]]
		return dp[N][K]


import math

class Solution:

	def __init__(self):
		self.dp = [[-1 for x in range(200)] for y in range(25)]

	def rec(self, i, x, k, arr, n):
		if i == n:
			if x == k:
				return 1
			else:
				return 0
		if self.dp[i][x] != -1:
			return self.dp[i][x]
		a1 = self.rec(i + 1, x ^ arr[i], k, arr, n)
		a2 = self.rec(i + 1, x, k, arr, n)
		ans = a1 + a2
		self.dp[i][x] = ans
		return ans

	def subsetXOR(self, arr, N, K):
		r = self.rec(0, 0, K, arr, N)
		return r


import math

class Solution:

	def subsetXOR(self, arr, N, K):
		maxi = int(math.sqrt(self.find_max(arr)))
		dp = [[0 for i in range(128)] for i in range(N)]
		dp[0][0] = dp[0][arr[0]] = 1
		for i in range(1, N):
			for j in range(128):
				dp[i][arr[i] ^ j] = dp[i - 1][arr[i] ^ j] + dp[i - 1][j]
		return dp[N - 1][K]

	def find_max(self, arr):
		mini = 0
		for i in range(N):
			mini = max(mini, int(arr[i]))
		return mini


import math

class Solution:

	def solve(self, arr, ind, tempXOR, k, N, memo):
		if ind == N:
			if tempXOR == k:
				return 1
			return 0
		if (ind, tempXOR) in memo.keys():
			return memo[ind, tempXOR]
		nonpick = self.solve(arr, ind + 1, tempXOR, k, N, memo)
		tempXOR ^= arr[ind]
		pick = self.solve(arr, ind + 1, tempXOR, k, N, memo)
		memo[ind, tempXOR] = pick + nonpick
		return memo[ind, tempXOR]

	def subsetXOR(self, arr, N, K):
		memo = {}
		return self.solve(arr, 0, 0, K, N, memo)


import math

class Solution:

	def subsetXOR(self, arr, N, K):

		def solve(n, xor, arr, k, memo, N):
			if n == N:
				if xor == k:
					return 1
				return 0
			if (n, xor) in memo:
				return memo[n, xor]
			pick = solve(n + 1, xor ^ arr[n], arr, k, memo, N)
			nonpick = solve(n + 1, xor, arr, k, memo, N)
			memo[n, xor] = pick + nonpick
			return memo[n, xor]
		memo = {}
		return solve(0, 0, arr, K, memo, N)


import math

class Solution:

	def printer(self, counts):
		for i in range(len(counts)):
			if counts[i] != 0:
				print(i, counts[i])

	def subsetXOR(self, arr, N, K):
		current = 0
		(counts, preCounts) = ([0] * 256, [0] * 256)
		result = 0
		for i in range(N):
			preCounts = counts
			counts = [0] * 256
			a = arr[i]
			_next = current ^ a
			for i in range(len(counts)):
				counts[i] = preCounts[i] + preCounts[_next ^ i]
			counts[_next] += 1
			current = _next
		return counts[K]


import math

class Solution:

	def subsetXOR(self, arr, N, K):

		def solve(i, n, k, arr, x):
			if i == n:
				return x == k
			if dp[i][x] != -1:
				return dp[i][x]
			take = solve(i + 1, n, k, arr, x ^ arr[i])
			leave = solve(i + 1, n, k, arr, x)
			dp[i][x] = take + leave
			return dp[i][x]
		dp = [[-1 for i in range(201)] for j in range(21)]
		return solve(0, N, K, arr, 0)