有一个大小为 $$$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$$$ ($$$1 \le n, m \le 20$$$, $$$0 \le k \le 10^{18}$$$) — 网格的高度和宽度,以及数字 $$$k$$$。
接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个整数,第 $$$i$$$ 行中的第 $$$j$$$ 元素是 $$$a_{i, j}$$$ ($$$0 \le a_{i, j} \le 10^{18}$$$)。
输出
打印一个整数 — 从 ($$$1, 1$$$) 到 ($$$n, m$$$) 的路径数,异或和等于 $$$k$$$。
示例
输入 #1
3 3 11 2 1 5 7 10 0 12 6 4
输出 #1
3
输入 #2
3 4 2 1 3 3 3 0 3 3 2 3 0 1 1
输出 #2
5
输入 #3
3 4 1000000000000000000 1 3 3 3 0 3 3 2 3 0 1 1
输出 #3
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)$$$。