{"problem":{"name":"XOR on Grid Path","description":{"content":"There is a grid with $N$ rows and $N$ columns. We denote by $(i, j)$ the square at the $i$\\-th $(1 \\leq i \\leq N)$ row from the top and $j$\\-th $(1 \\leq j \\leq N)$ column from the left.   Square $(i, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc271_f"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $N$ rows and $N$ columns. We denote by $(i, j)$ the square at the $i$\\-th $(1 \\leq i \\leq N)$ row from the top and $j$\\-th $(1 \\leq j \\leq N)$ column from the left.  \nSquare $(i, j)$ has a non-negative integer $a_{i, j}$ written on it.\nWhen you are at square $(i, j)$, you can move to either square $(i+1, j)$ or $(i, j+1)$. Here, you are not allowed to go outside the grid.\nFind the number of ways to travel from square $(1, 1)$ to square $(N, N)$ such that the exclusive logical sum of the integers written on the squares visited (including $(1, 1)$ and $(N, N)$) is $0$.\nWhat is the exclusive logical sum? The exclusive logical sum $a \\oplus b$ of two integers $a$ and $b$ is defined as follows.\n\n*   The $2^k$'s place ($k \\geq 0$) in the binary notation of $a \\oplus b$ is $1$ if exactly one of the $2^k$'s places in the binary notation of $a$ and $b$ is $1$; otherwise, it is $0$.\n\nFor example, $3 \\oplus 5 = 6$ (In binary notation: $011 \\oplus 101 = 110$).  \nIn general, the exclusive logical sum of $k$ integers $p_1, \\dots, p_k$ is defined as $(\\cdots ((p_1 \\oplus p_2) \\oplus p_3) \\oplus \\cdots \\oplus p_k)$. We can prove that it is independent of the order of $p_1, \\dots, p_k$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 20$\n*   $0 \\leq a_{i, j} \\lt 2^{30} \\, (1 \\leq i, j \\leq N)$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$a_{1, 1}$ $\\ldots$ $a_{1, N}$\n$\\vdots$\n$a_{N, 1}$ $\\ldots$ $a_{N, N}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc271_f","tags":[],"sample_group":[["3\n1 5 2\n7 0 5\n4 2 3","2\n\nThe following two ways satisfy the condition:\n\n*   $(1, 1) \\rightarrow (1, 2) \\rightarrow (1, 3) \\rightarrow (2, 3) \\rightarrow (3, 3)$;\n*   $(1, 1) \\rightarrow (2, 1) \\rightarrow (2, 2) \\rightarrow (2, 3) \\rightarrow (3, 3)$."],["2\n1 2\n2 1","0"],["10\n1 0 1 0 0 1 0 0 0 1\n0 0 0 1 0 1 0 1 1 0\n1 0 0 0 1 0 1 0 0 0\n0 1 0 0 0 1 1 0 0 1\n0 0 1 1 0 1 1 0 1 0\n1 0 0 0 1 0 0 1 1 0\n1 1 1 0 0 0 1 1 0 0\n0 1 1 0 0 1 1 0 1 0\n1 0 1 1 0 0 0 0 0 0\n1 0 1 1 0 0 1 1 1 0","24307"]],"created_at":"2026-03-03 11:01:13"}}