题目描述

有一个大小为 $n \times m$ 的矩形网格。每个格子上写有一个数字；第 $(i, j)$ 个格子上的数字为 $a_{i, j}$。你的任务是计算从左上角格子 $(1, 1)$ 到右下角格子 $(n, m)$ 的路径数，要求满足以下约束：

• 你只能向右或向下移动。具体来说，从格子 $(i, j)$ 可以移动到 $(i, j + 1)$ 或 $(i + 1, j)$，目标格子不能超出网格范围。
• 从 $(1, 1)$ 到 $(n, m)$ 路径上所有数字的异或和必须等于 $k$（异或操作是按位异或，在 Java 或 C++ 中用 '^' 表示，在 Pascal 中用 "xor" 表示）。

请计算在给定网格中满足条件的路径数。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$——网格的高度、宽度和目标异或值 $k$。

接下来的 $n$ 行，每行包含 $m$ 个整数，第 $i$ 行第 $j$ 个元素为 $a_{i, j}$。

输出格式

输出一个整数，表示从 $(1, 1)$ 到 $(n, m)$ 且异或和等于 $k$ 的路径数。

3 3 11
2 1 5
7 10 0
12 6 4

3

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

5

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

0

说明 / 提示

第一个样例的所有路径：

• $(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)$。

第二个样例的所有路径：

• $(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)$。

由 ChatGPT 4.1 翻译

数据范围

（$1 \le n, m \le 20$，$0 \le k \le 10^{18}$）

（$0 \le a_{i, j} \le 10^{18}$）