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: introductory

Starter code:

Solutions:
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)

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 list(t[i-1][j].items()):
			t[i][j][num^b[i][j]] = cnt
		for num,cnt in list(t[i][j-1].items()):
			if num^b[i][j] in list(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
#print(b)

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 list(t2[i+1][j].items()):
			t2[i][j][num^b[i][j]] = cnt
		for num,cnt in list(t2[i][j+1].items()):
			if num^b[i][j] in list(t2[i][j].keys()):
				t2[i][j][num^b[i][j]] += cnt
			else:
				t2[i][j][num^b[i][j]] = cnt

res = 0

#print(t)
#print(t2)

for i in range(n):
	for j in range(m):
		if i+j != limit:
			continue
		tk = set(t[i][j].keys())
		for k2 in list(t2[i][j].keys()):
			if (k2^k) in tk:
				res += t2[i][j][k2] * t[i][j][k2^k]
#				print(k2, t2[i][j][k2], t[i][j][k2^k])

print(res)

#print(t)
#try:	
#	print(t[n-1][m-1][k])
#except KeyError:
#	print(0)



cnt = {}
for i in range(22):
    cnt[i] = {}

#print(cnt)

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:
        #print('yes')
        if now in cnt[x]:
            cnt[x][now] += 1
        else:
            cnt[x][now] = 1
        return

    go(x+1,y,now)
    go(x,y+1,now)

ans = 0

def goRev(x,y,now):
    if check(x,y) == False:
        return

    if x + y == m - 1:
        cur = k ^ now
        if cur in cnt[x]:
            nonlocal ans
            #print(ans)
            ans += cnt[x][cur]
        return

    now ^= arr[x][y]
    goRev(x-1,y,now)
    goRev(x,y-1,now)


go(0,0,0)
goRev(n-1,m-1,0)

print(ans)
    


















cnt = {}
for i in range(22):
    cnt[i] = {}

#print(cnt)

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:
        #print('yes')
        if now in cnt[x]:
            cnt[x][now] += 1
        else:
            cnt[x][now] = 1
        return

    go(x+1,y,now)
    go(x,y+1,now)

ans = 0

def goRev(x,y,now):
    if check(x,y) == False:
        return

    if x + y == m - 1:
        cur = k ^ now
        if cur in cnt[x]:
            nonlocal ans
            #print(ans)
            ans += cnt[x][cur]
        return

    now ^= arr[x][y]
    goRev(x-1,y,now)
    goRev(x,y-1,now)


go(0,0,0)
goRev(n-1,m-1,0)

print(ans)

d = {}
for i in range(22):
    d[i] = {}

#print(cnt)

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:
        #print('yes')
        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)

ans = 0

def goRev(x,y,now):
    if check(x,y) == False:
        return

    if x + y == m - 1:
        cur = k ^ now
        if cur in d[x]:
            nonlocal ans
            #print(ans)
            ans += d[x][cur]
        return

    now ^= arr[x][y]
    goRev(x-1,y,now)
    goRev(x,y-1,now)


go(0,0,0)
goRev(n-1,m-1,0)

print(ans)

d = {}
ans = 0
for i in range(22):
    d[i] = {}

#print(cnt)

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:
        #print('yes')
        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(x,y,now):
    if check(x,y) == False:
        return

    if x + y == m - 1:
        cur = k ^ now
        if cur in d[x]:
            nonlocal ans
            #print(ans)
            ans += d[x][cur]
        return

    now ^= arr[x][y]
    goRev(x-1,y,now)
    goRev(x,y-1,now)


go(0,0,0)
goRev(n-1,m-1,0)

print(ans)

d = {}
ans = 0
for i in range(22):
    d[i] = {}

#print(cnt)

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:
        #print('yes')
        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 goRev111(x,y,now):
    if check(x,y) == False:
        return

    if x + y == m - 1:
        cur = k ^ now
        if cur in d[x]:
            nonlocal ans
            #print(ans)
            ans += d[x][cur]
        return

    now ^= arr[x][y]
    goRev111(x-1,y,now)
    goRev111(x,y-1,now)


go(0,0,0)
goRev111(n-1,m-1,0)

print(ans)

d = {}
ans = 0
for i in range(22):
    d[i] = {}

#print(cnt)

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:
        #print('yes')
        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]:
            nonlocal ans
            #print(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)



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:
        #print('yes')
        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
            #print(ans)
            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(d)
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
        #print(tmp)
        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(d)
print(re)

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)
    else:
        if abs(x - n) + abs(y - m) + 1 == m:
            # print(x, y, mk)
            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)
# print(matrix)
d = [[{} for _ in range(m)] for _ in range(n)]
# print(d)
middle = (n + m - 2) // 2
# print(middle)
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(d)
print(answer)


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)


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 = []
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 list(d.keys()):
        if key in d and key in e:
            wae += d[key] * e[key]

print(wae)


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()

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
#print(s, t)
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
#print(DS)
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
        #print(skey, sres)
        ans += DS[skey][sres]
print(ans)