该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有一个大小为 $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$。

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

Format

Input

输入的第一行包含三个整数 $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}$）。

Output

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

Samples

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

Note

第一个样例的所有路径：

• $(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3)$；
• $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (3, 3)$；
• $(1, 1) \to (1, 2) \to (2, 2) \to (3, 2) \to (3, 3)$。

第二个样例的所有路径：

• $(1, 1) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3) \to (3, 4)$；
• $(1, 1) \to (2, 1) \to (2, 2) \to (3, 2) \to (3, 3) \to (3, 4)$；
• $(1, 1) \to (2, 1) \to (2, 2) \to (2, 3) \to (2, 4) \to (3, 4)$；
• $(1, 1) \to (1, 2) \to (2, 2) \to (2, 3) \to (3, 3) \to (3, 4)$；
• $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (3, 3) \to (3, 4)$。