{"raw_statement":[{"iden":"statement","content":"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:\n\n*   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.\n*   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).\n\nFind the number of such paths in the given grid."},{"iden":"input","content":"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$.\n\nThe 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}$)."},{"iden":"output","content":"Print one integer — the number of paths from ($1, 1$) to ($n, m$) with _xor_ sum equal to $k$."},{"iden":"examples","content":"Input\n\n3 3 11\n2 1 5\n7 10 0\n12 6 4\n\nOutput\n\n3\n\nInput\n\n3 4 2\n1 3 3 3\n0 3 3 2\n3 0 1 1\n\nOutput\n\n5\n\nInput\n\n3 4 1000000000000000000\n1 3 3 3\n0 3 3 2\n3 0 1 1\n\nOutput\n\n0"},{"iden":"note","content":"All the paths from the first example:\n\n*   $(1, 1) \\rightarrow (2, 1) \\rightarrow (3, 1) \\rightarrow (3, 2) \\rightarrow (3, 3)$;\n*   $(1, 1) \\rightarrow (2, 1) \\rightarrow (2, 2) \\rightarrow (2, 3) \\rightarrow (3, 3)$;\n*   $(1, 1) \\rightarrow (1, 2) \\rightarrow (2, 2) \\rightarrow (3, 2) \\rightarrow (3, 3)$.\n\nAll the paths from the second example:\n\n*   $(1, 1) \\rightarrow (2, 1) \\rightarrow (3, 1) \\rightarrow (3, 2) \\rightarrow (3, 3) \\rightarrow (3, 4)$;\n*   $(1, 1) \\rightarrow (2, 1) \\rightarrow (2, 2) \\rightarrow (3, 2) \\rightarrow (3, 3) \\rightarrow (3, 4)$;\n*   $(1, 1) \\rightarrow (2, 1) \\rightarrow (2, 2) \\rightarrow (2, 3) \\rightarrow (2, 4) \\rightarrow (3, 4)$;\n*   $(1, 1) \\rightarrow (1, 2) \\rightarrow (2, 2) \\rightarrow (2, 3) \\rightarrow (3, 3) \\rightarrow (3, 4)$;\n*   $(1, 1) \\rightarrow (1, 2) \\rightarrow (1, 3) \\rightarrow (2, 3) \\rightarrow (3, 3) \\rightarrow (3, 4)$."}],"translated_statement":[{"iden":"statement","content":"有一个大小为 $n \\times m$ 的矩形网格。每个格子上写有一个数字，格子 $(i, j)$ 上的数字为 $a_{(i, j)}$。你的任务是计算从左上角格子 $(1, 1)$ 到右下角格子 $(n, m)$ 的路径数量，满足以下条件：\n\n求出满足上述条件的路径数量。\n\n输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \\leq n, m \\leq 20$，$0 \\leq k \\leq 10^{18}$），分别表示网格的高度、宽度和数字 $k$。\n\n接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个元素为 $a_{(i, j)}$（$0 \\leq a_{(i, j)} \\leq 10^{18}$）。\n\n请输出一个整数——从 $(1, 1)$ 到 $(n, m)$ 的路径中，异或和等于 $k$ 的路径数量。\n\n第一个示例中的所有路径：\n\n第二个示例中的所有路径：\n\n"},{"iden":"input","content":"输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \\leq n, m \\leq 20$，$0 \\leq k \\leq 10^{18}$），分别表示网格的高度、宽度和数字 $k$。接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个元素为 $a_{(i, j)}$（$0 \\leq a_{(i, j)} \\leq 10^{18}$）。"},{"iden":"output","content":"请输出一个整数——从 $(1, 1)$ 到 $(n, m)$ 的路径中，异或和等于 $k$ 的路径数量。"},{"iden":"examples","content":"输入\n3 3 11\n2 1 5\n7 10 0\n12 6 4\n输出\n3\n\n输入\n3 4 2\n1 3 3 3\n0 3 3 2\n3 0 1 1\n输出\n5\n\n输入\n3 4 1000000000000000000\n1 3 3 3\n0 3 3 2\n3 0 1 1\n输出\n0"},{"iden":"note","content":"第一个示例中的所有路径：\n$(1, 1) \\to (2, 1) \\to (3, 1) \\to (3, 2) \\to (3, 3)$；\n$(1, 1) \\to (2, 1) \\to (2, 2) \\to (2, 3) \\to (3, 3)$；\n$(1, 1) \\to (1, 2) \\to (2, 2) \\to (3, 2) \\to (3, 3)$。\n\n第二个示例中的所有路径：\n$(1, 1) \\to (2, 1) \\to (3, 1) \\to (3, 2) \\to (3, 3) \\to (3, 4)$；\n$(1, 1) \\to (2, 1) \\to (2, 2) \\to (3, 2) \\to (3, 3) \\to (3, 4)$；\n$(1, 1) \\to (2, 1) \\to (2, 2) \\to (2, 3) \\to (2, 4) \\to (3, 4)$；\n$(1, 1) \\to (1, 2) \\to (2, 2) \\to (2, 3) \\to (3, 3) \\to (3, 4)$；\n$(1, 1) \\to (1, 2) \\to (1, 3) \\to (2, 3) \\to (3, 3) \\to (3, 4)$。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the dimensions of the grid.  \nLet $ k \\in \\mathbb{Z}_{\\geq 0} $ be the target XOR value.  \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}_{\\geq 0}^{n \\times m} $ be the grid, where $ a_{i,j} $ is the value in cell $ (i,j) $.  \n\nA *path* is a sequence of cells $ (i_1, j_1), (i_2, j_2), \\dots, (i_\\ell, j_\\ell) $ such that:  \n- $ (i_1, j_1) = (1,1) $,  \n- $ (i_\\ell, j_\\ell) = (n,m) $,  \n- For all $ t \\in \\{1, \\dots, \\ell-1\\} $, $ (i_{t+1}, j_{t+1}) $ is either $ (i_t + 1, j_t) $ or $ (i_t, j_t + 1) $.  \n\nThe *XOR sum* of a path is the bitwise XOR of all $ a_{i_t,j_t} $ along the path:  \n$$\n\\bigoplus_{t=1}^{\\ell} a_{i_t, j_t}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 20 $  \n2. $ 0 \\leq k \\leq 10^{18} $  \n3. $ 0 \\leq a_{i,j} \\leq 10^{18} $ for all $ i \\in \\{1,\\dots,n\\}, j \\in \\{1,\\dots,m\\} $\n\n**Objective**  \nCompute the number of paths from $ (1,1) $ to $ (n,m) $ such that the XOR sum of the values along the path equals $ k $.","simple_statement":null,"has_page_source":false}