There is a rectangular grid of size $n \times m$. Each cell has a number written on it; the number on the cell ($i, j$) is $a_{i, j}$. Your task is to calculate the number of paths from the upper-left cell ($1, 1$) to the bottom-right cell ($n, m$) meeting the following constraints:

  You can move to the right or to the bottom only. Formally, from the cell ($i, j$) you may move to the cell ($i, j + 1$) or to the cell ($i + 1, j$). The target cell can't be outside of the grid.  The xor of all the numbers on the path from the cell ($1, 1$) to the cell ($n, m$) must be equal to $k$ (xor operation is the bitwise exclusive OR, it is represented as '^' in Java or C++ and "xor" in Pascal). 

Find the number of such paths in the given grid.


-----Input-----

The first line of the input contains three integers $n$, $m$ and $k$ ($1 \le n, m \le 20$, $0 \le k \le 10^{18}$) — the height and the width of the grid, and the number $k$.

The next $n$ lines contain $m$ integers each, the $j$-th element in the $i$-th line is $a_{i, j}$ ($0 \le a_{i, j} \le 10^{18}$).


-----Output-----

Print one integer — the number of paths from ($1, 1$) to ($n, m$) with xor sum equal to $k$.


-----Examples-----
Input
3 3 11
2 1 5
7 10 0
12 6 4

Output
3

Input
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1

Output
5

Input
3 4 1000000000000000000
1 3 3 3
0 3 3 2
3 0 1 1

Output
0



-----Note-----

All the paths from the first example:   $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$;  $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$;  $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$. 

All the paths from the second example:   $(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$;  $(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$.

Difficulty: HARD
Tags: Dynamic programming

Bit manipulation

Complete search
Skill types: Dynamic programming

Bit manipulation

Complete search

Starter code:

Solutions:
d = {}
ans = 0
for i in range(22):
	d[i] = {}
(n, m, k) = list(map(int, input().split()))
arr = [list(map(int, input().split())) for i in range(n)]

def check(x, y):
	if x < 0 or x >= n or y < 0 or (y >= m):
		return False
	else:
		return True

def go(x, y, now):
	if check(x, y) == False:
		return
	now ^= arr[x][y]
	if x + y == m - 1:
		if now in d[x]:
			d[x][now] += 1
		else:
			d[x][now] = 1
		return
	go(x + 1, y, now)
	go(x, y + 1, now)

def goRev(i, j, now):
	if check(i, j) == False:
		return
	if i + j == m - 1:
		cur = k ^ now
		if cur in d[i]:
			global ans
			ans += d[i][cur]
		return
	now ^= arr[i][j]
	goRev(i - 1, j, now)
	goRev(i, j - 1, now)
go(0, 0, 0)
goRev(n - 1, m - 1, 0)
print(ans)


def go_up_to_down(w, h, value, steps):
	value ^= matrix[h][w]
	if steps == half_steps:
		if value not in counts[h][w]:
			counts[h][w][value] = 0
		counts[h][w][value] += 1
		return
	if w < width - 1:
		go_up_to_down(w + 1, h, value, steps + 1)
	if h < height - 1:
		go_up_to_down(w, h + 1, value, steps + 1)

def go_down_to_up(w, h, value, steps, count_ways):
	if steps == width + height - 2 - half_steps:
		if value ^ res_find in counts[h][w]:
			count_ways += counts[h][w][value ^ res_find]
		return count_ways
	delta = 0
	if w > 0:
		delta += go_down_to_up(w - 1, h, value ^ matrix[h][w], steps + 1, count_ways)
	if h > 0:
		delta += go_down_to_up(w, h - 1, value ^ matrix[h][w], steps + 1, count_ways)
	return count_ways + delta
(height, width, res_find) = [int(num) for num in input().split()]
matrix = []
for h in range(height):
	row = [int(num) for num in input().split()]
	matrix.append(row)
counts = [[dict()] * width for h in range(height)]
half_steps = (width + height - 2) // 2
go_up_to_down(0, 0, 0, 0)
count_ways = go_down_to_up(width - 1, height - 1, 0, 0, 0)
print(count_ways)


import math
from collections import defaultdict
import sys

def main():
	(n, m, k) = list(map(int, input().split()))
	g = [[] for _ in range(n)]
	for i in range(n):
		g[i] = list(map(int, input().split()))
	cnt = [[defaultdict(int) for _ in range(m)] for _ in range(n)]
	all = n + m - 2
	half = all // 2
	res = [0]

	def go_start(x, y, val, steps):
		val ^= g[x][y]
		if steps == half:
			cnt[x][y][val] += 1
			return
		if x + 1 < n:
			go_start(x + 1, y, val, steps + 1)
		if y + 1 < m:
			go_start(x, y + 1, val, steps + 1)

	def go_end(x, y, val, steps):
		if steps + half == all:
			comp = k ^ val
			if comp in cnt[x][y]:
				res[0] += cnt[x][y][comp]
			return
		val ^= g[x][y]
		if x > 0:
			go_end(x - 1, y, val, steps + 1)
		if y > 0:
			go_end(x, y - 1, val, steps + 1)
	go_start(0, 0, 0, 0)
	go_end(n - 1, m - 1, 0, 0)
	print(res[0])

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
(n, m, k) = list(map(int, input().split()))
a = [[0 for j in range(m)] for i in range(n)]
for i in range(n):
	a[i] = list(map(int, input().split()))
total = n + m - 2
half = total // 2
b = defaultdict(dict)

def upper(i, j, val, cnt):
	val ^= a[i][j]
	if cnt == half:
		s = str(i) + ' ' + str(j)
		if val in b[s]:
			b[s][val] += 1
		else:
			b[s][val] = 1
		return
	if i + 1 < n:
		upper(i + 1, j, val, cnt + 1)
	if j + 1 < m:
		upper(i, j + 1, val, cnt + 1)
answer = 0

def lower(i, j, val, cnt):
	nonlocal answer
	s = str(i) + ' ' + str(j)
	if cnt == total - half:
		aim = k ^ val
		if aim in b[s]:
			answer += b[s][aim]
		return
	if i > 0:
		lower(i - 1, j, val ^ a[i][j], cnt + 1)
	if j > 0:
		lower(i, j - 1, val ^ a[i][j], cnt + 1)
upper(0, 0, 0, 0)
lower(n - 1, m - 1, 0, 0)
print(answer)


(n, m, k) = list(map(int, input().split()))
A = [list(map(int, input().split())) for _ in range(n)]
if n == 1 and m == 1:
	if A[0][0] == k:
		print(1)
	else:
		print(0)
	return
import itertools
ans = 0
s = (n - 1 + m - 1) // 2
t = n - 1 + m - 1 - s
from collections import defaultdict
DS = [defaultdict(lambda : 0) for key in range(n)]
for i in range(2 ** s):
	L = [0] * s
	for j in range(s):
		if i >> j & 1:
			L[j] = 1
	key = sum(L)
	if key > n - 1:
		continue
	y = 0
	x = 0
	res = A[0][0]
	for l in L:
		if l == 1:
			y += 1
		else:
			x += 1
		if 0 <= y < n and 0 <= x < m:
			res ^= A[y][x]
		else:
			break
	else:
		DS[key][res] += 1
ans = 0
for i in range(2 ** t):
	L = [0] * t
	for j in range(t):
		if i >> j & 1:
			L[j] = 1
	tkey = sum(L)
	if tkey > n - 1:
		continue
	y = n - 1
	x = m - 1
	res = A[n - 1][m - 1]
	for (idx, l) in enumerate(L):
		if idx == len(L) - 1:
			continue
		if l == 1:
			y -= 1
		else:
			x -= 1
		if 0 <= y < n and 0 <= x < m:
			res ^= A[y][x]
		else:
			break
	else:
		skey = n - 1 - tkey
		sres = res ^ k
		ans += DS[skey][sres]
print(ans)


from collections import defaultdict
(n, m, aim) = list(map(int, input().split()))
g = [[0 for i in range(m + 1)] for j in range(n + 1)]
for i in range(n):
	ls = [int(i) for i in input().split()]
	for j in range(m):
		g[i + 1][j + 1] = ls[j]
ans = 0
dp = defaultdict(int)

def search(x, y, is_l, mk):
	if x < 1 or y < 1 or x > n or (y > m):
		return
	if is_l:
		mk ^= g[x][y]
		if x + y - 1 == n:
			dp[x, y, mk] += 1
		else:
			search(x + 1, y, is_l, mk)
			search(x, y + 1, is_l, mk)
	elif abs(x - n) + abs(y - m) + 1 == m:
		nonlocal ans
		ans += dp[x, y, mk]
	else:
		mk ^= g[x][y]
		search(x - 1, y, is_l, mk)
		search(x, y - 1, is_l, mk)
search(1, 1, True, 0)
search(n, m, False, aim)
print(ans)


(n, m, k) = list(map(int, input().split()))
matrix = []
for _ in range(n):
	row = list(map(int, input().split()))
	matrix.append(row)
d = [[{} for _ in range(m)] for _ in range(n)]
middle = (n + m - 2) // 2
answer = 0

def upleft(x, y, acc, count):
	val = matrix[y][x] ^ acc
	if count == middle:
		if d[y][x].get(val) == None:
			d[y][x][val] = 1
			return
		else:
			d[y][x][val] += 1
			return
	else:
		if x + 1 < m:
			upleft(x + 1, y, val, count + 1)
		if y + 1 < n:
			upleft(x, y + 1, val, count + 1)

def downright(x, y, acc, count):
	nonlocal answer
	if count == n + m - 2 - middle:
		complement = k ^ acc
		if d[y][x].get(complement) != None:
			answer += d[y][x][complement]
		return
	else:
		val = matrix[y][x] ^ acc
		if x - 1 >= 0:
			downright(x - 1, y, val, count + 1)
		if y - 1 >= 0:
			downright(x, y - 1, val, count + 1)
upleft(0, 0, 0, 0)
downright(m - 1, n - 1, 0, 0)
print(answer)


(n, m, k) = list(map(int, input().split()))
b = [list(map(int, input().split())) for i in range(n)]
t = [[None for i in range(m)] for j in range(n)]
t2 = [[None for i in range(m)] for j in range(n)]
t[0][0] = {b[0][0]: 1}
for i in range(1, m):
	t[0][i] = {list(t[0][i - 1].keys())[0] ^ b[0][i]: 1}
for i in range(1, n):
	t[i][0] = {list(t[i - 1][0].keys())[0] ^ b[i][0]: 1}
limit = (n + m - 2) // 2
for i in range(1, n):
	for j in range(1, m):
		if i + j > limit:
			continue
		t[i][j] = {}
		for (num, cnt) in t[i - 1][j].items():
			t[i][j][num ^ b[i][j]] = cnt
		for (num, cnt) in t[i][j - 1].items():
			if num ^ b[i][j] in t[i][j].keys():
				t[i][j][num ^ b[i][j]] += cnt
			else:
				t[i][j][num ^ b[i][j]] = cnt
for i in range(n):
	for j in range(m):
		if i + j == limit:
			b[i][j] = 0
t2[n - 1][m - 1] = {b[n - 1][m - 1]: 1}
for i in range(m - 2, -1, -1):
	t2[n - 1][i] = {list(t2[n - 1][i + 1].keys())[0] ^ b[n - 1][i]: 1}
for i in range(n - 2, -1, -1):
	t2[i][m - 1] = {list(t2[i + 1][m - 1].keys())[0] ^ b[i][m - 1]: 1}
for i in range(n - 2, -1, -1):
	for j in range(m - 2, -1, -1):
		if i + j < limit:
			continue
		t2[i][j] = {}
		for (num, cnt) in t2[i + 1][j].items():
			t2[i][j][num ^ b[i][j]] = cnt
		for (num, cnt) in t2[i][j + 1].items():
			if num ^ b[i][j] in t2[i][j].keys():
				t2[i][j][num ^ b[i][j]] += cnt
			else:
				t2[i][j][num ^ b[i][j]] = cnt
res = 0
for i in range(n):
	for j in range(m):
		if i + j != limit:
			continue
		tk = set(t[i][j].keys())
		for k2 in t2[i][j].keys():
			if k2 ^ k in tk:
				res += t2[i][j][k2] * t[i][j][k2 ^ k]
print(res)


from collections import defaultdict
import itertools
import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
l = n + m - 2
l0 = l // 2
l1 = (l + 1) // 2
p = [i for i in range(l0)]
xx = defaultdict(lambda : defaultdict(lambda : 0))
for i in range(l0 + 1):
	ok = 1
	for p0 in itertools.combinations(p, i):
		s = set(p0)
		now = 0
		(x, y) = (0, 0)
		for j in range(l0):
			now ^= a[x][y]
			if j in s:
				x += 1
			else:
				y += 1
			if not 0 <= x < n or not 0 <= y < m:
				ok = 0
				break
		if not ok:
			break
		now ^= a[x][y]
		xx[x, y][now] += 1
p = [i for i in range(l1)]
ans = 0
for i in range(l1 + 1):
	ok = 1
	for p0 in itertools.combinations(p, i):
		s = set(p0)
		now = 0
		(x, y) = (n - 1, m - 1)
		for j in range(l1):
			now ^= a[x][y]
			if j in s:
				x -= 1
			else:
				y -= 1
			if not 0 <= x < n or not 0 <= y < m:
				ok = 0
				break
		if not ok:
			break
		ans += xx[x, y][now ^ k]
print(ans)


(n, m, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
if n > m:
	d = []
	for i in range(m):
		d.append([])
		for j in range(n):
			d[i].append(a[j][i])
	a = d
	(n, m) = (m, n)
b = []
for i in range(n):
	temp = []
	for j in range(m):
		temp.append([])
	b.append(temp)
for i in range((n + m) // 2):
	for j in range(min(i + 1, m, n)):
		if i == 0:
			b[j][i - j].append(a[j][i - j])
		elif j == 0:
			b[j][i - j].append(b[j][i - j - 1][0] ^ a[j][i - j])
		elif j == i:
			b[j][i - j].append(b[j - 1][i - j][0] ^ a[j][i - j])
		else:
			for x in b[j][i - j - 1] + b[j - 1][i - j]:
				b[j][i - j].append(x ^ a[j][i - j])
c = []
for i in range(n):
	temp = []
	for j in range(m):
		temp.append([])
	c.append(temp)
for i in range((n + m + 1) // 2):
	for j in range(min(i + 1, m, n)):
		if i == 0:
			c[n - 1 - j][m - 1 - (i - j)].append(k)
		elif j == 0:
			c[n - 1 - j][m - 1 - (i - j)].append(c[n - 1 - j][m - 1 - (i - j - 1)][0] ^ a[n - 1 - j][m - 1 - (i - j - 1)])
		elif j == i:
			c[n - 1 - j][m - 1 - (i - j)].append(c[n - 1 - (j - 1)][m - 1 - (i - j)][0] ^ a[n - 1 - (j - 1)][m - 1 - (i - j)])
		else:
			for x in c[n - 1 - j][m - 1 - (i - j - 1)]:
				c[n - 1 - j][m - 1 - (i - j)].append(x ^ a[n - 1 - j][m - 1 - (i - j - 1)])
			for x in c[n - 1 - (j - 1)][m - 1 - (i - j)]:
				c[n - 1 - j][m - 1 - (i - j)].append(x ^ a[n - 1 - (j - 1)][m - 1 - (i - j)])
wae = 0
i = (n + m) // 2 - 1
for j in range(min(m, n)):
	d = {}
	e = {}
	for l1 in b[j][i - j]:
		if not l1 in d:
			d[l1] = 0
		d[l1] += 1
	for l2 in c[j][i - j]:
		if not l2 in e:
			e[l2] = 0
		e[l2] += 1
	for key in d.keys():
		if key in d and key in e:
			wae += d[key] * e[key]
print(wae)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def lcm(a, b):
	return abs(a // gcd(a, b) * b)

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def comb(n, r):
	if n < r:
		return 0
	else:
		return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def yes():
	print('Yes')

def no():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
rng = range

def solve():
	(n, m, k) = sep()
	ar = []
	for _ in rng(n):
		ar.append(lis())
	total = n + m - 2
	first = total // 2
	second = total - first
	d1 = defaultdict(int)

	def isvalid(i, j):
		if 0 <= i < n and 0 <= j < m:
			return 1
		return 0
	for mask in rng(1 << first):
		curry = 0
		currx = 0
		currxor = ar[0][0]
		f = 1
		for i in range(first):
			if mask & 1 << i:
				if not isvalid(currx + 1, curry):
					f = -1
					break
				currx += 1
				currxor ^= ar[currx][curry]
			else:
				if not isvalid(currx, curry + 1):
					f = -1
					break
				curry += 1
				currxor ^= ar[currx][curry]
		if f == 1:
			d1[currx, curry, currxor] += 1
	ans = 0
	for mask in rng(1 << second):
		curry = m - 1
		currx = n - 1
		currxor = ar[n - 1][m - 1]
		f = 1
		for i in range(second):
			if mask & 1 << i:
				if not isvalid(currx - 1, curry):
					f = -1
					break
				currx -= 1
				currxor ^= ar[currx][curry]
			else:
				if not isvalid(currx, curry - 1):
					f = -1
					break
				curry -= 1
				currxor ^= ar[currx][curry]
		if f == 1:
			ans += d1[currx, curry, currxor ^ k ^ ar[currx][curry]]
	print(ans)
solve()


d = {}
for i in range(22):
	d[i] = {}
(n, m, k) = list(map(int, input().split()))
l = [list(map(int, input().split())) for i in range(n)]

def check(x, y):
	if x < 0 or x >= n or y < 0 or (y >= m):
		return False
	else:
		return True

def go(x, y, now):
	if check(x, y) == False:
		return
	now ^= l[x][y]
	if x + y == m - 1:
		if now in d[x]:
			d[x][now] += 1
		else:
			d[x][now] = 1
		return
	go(x + 1, y, now)
	go(x, y + 1, now)
re = 0

def goRev(i, j, now):
	if check(i, j) == False:
		return
	if i + j == m - 1:
		cur = k ^ now
		if cur in d[i]:
			nonlocal re
			re += d[i][cur]
		return
	now ^= l[i][j]
	goRev(i - 1, j, now)
	goRev(i, j - 1, now)
go(0, 0, 0)
goRev(n - 1, m - 1, 0)
print(re)


(n, m, k) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(n)]
re = 0
half = (m + n - 2) // 2
d = [dict() for _ in range(22)]

def forward(i, j, value):
	if i >= n or j >= m:
		return
	value ^= l[i][j]
	if i + j == half:
		if value in d[i]:
			d[i][value] += 1
		else:
			d[i][value] = 1
		return None
	forward(i + 1, j, value)
	forward(i, j + 1, value)

def backward(i, j, value):
	if i < 0 or j < 0:
		return
	if i + j == half:
		tmp = k ^ value
		if tmp in d[i]:
			nonlocal re
			re += d[i][tmp]
		return None
	value ^= l[i][j]
	backward(i - 1, j, value)
	backward(i, j - 1, value)
forward(0, 0, 0)
backward(n - 1, m - 1, 0)
print(re)


import atexit, io, sys, collections, math, heapq, fractions, copy, os, functools
import sys
import random
import collections
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
(n, m, k) = map(int, input().split())
mat = [list(map(int, input().split())) for i in range(n)]
half = (n + m - 2) // 2
cc = [[collections.Counter() for j in range(len(mat[0]))] for i in range(len(mat))]

def dfs(i, j, ongoing, cc, half, mat):
	if half == 0:
		cc[i][j][ongoing] += 1
		return
	if i + 1 < len(mat):
		dfs(i + 1, j, ongoing ^ mat[i + 1][j], cc, half - 1, mat)
	if j + 1 < len(mat[0]):
		dfs(i, j + 1, ongoing ^ mat[i][j + 1], cc, half - 1, mat)
dfs(0, 0, mat[0][0], cc, half, mat)
ans = [0]

def dfs2(i, j, ongoing, cc, half, mat, k):
	if half == 0:
		ans[0] += cc[i][j][k ^ ongoing ^ mat[i][j]]
		return
	if i - 1 >= 0:
		dfs2(i - 1, j, ongoing ^ mat[i - 1][j], cc, half - 1, mat, k)
	if j - 1 >= 0:
		dfs2(i, j - 1, ongoing ^ mat[i][j - 1], cc, half - 1, mat, k)
dfs2(len(mat) - 1, len(mat[0]) - 1, mat[n - 1][m - 1], cc, n + m - 2 - half, mat, k)
print(ans[0])


from collections import *
(n, m, k) = map(int, input().split())
b = [[int(v) for v in input().split()] for _ in range(n)]
if m < n:
	a = [[b[j][i] for j in range(n)] for i in range(m)]
	b = a
	(m, n) = (n, m)
cntrs = [Counter() for _ in range(n)]
d = (n + m - 1) // 2
for i in range(1 << d):
	ones = bin(i).count('1')
	z = d - ones
	if ones >= n or z >= m:
		continue
	xor = b[0][0]
	(x, y) = (0, 0)
	for j in range(d):
		if i & 1 << j:
			x += 1
		else:
			y += 1
		xor ^= b[x][y]
	cntrs[x][xor] += 1
sm = 0
sleft = n + m - 2 - d
for i in range(1 << sleft):
	ones = bin(i).count('1')
	z = sleft - ones
	if ones >= n or z >= m:
		continue
	xor = b[n - 1][m - 1]
	(x, y) = (n - 1, m - 1)
	for j in range(sleft):
		if i & 1 << j:
			x -= 1
		else:
			y -= 1
		xor ^= b[x][y]
	xor ^= b[x][y] ^ k
	sm += cntrs[x][xor]
print(sm)