You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

有一个 $n \times m$ 的矩形网格，每个格子 $(i, j)$ 上都有一个非负整数 $a_{i,j}$。 你现在位于左上角 $(1, 1)$，需要移动到右下角 $(n, m)$。 在每一步中，你只能向右移动一格，或者向下移动一格。 当你经过一个格子时，你会拾取该格子上的数字（包括起点和终点）。 你的目标是：寻找有多少条路径，使得路径上所有数字的 按位异或和 恰好等于给定的目标值 $k$。

Input Format

第一行包含三个整数 $n, m, k$。 接下来 $n$ 行，每行包含 $m$ 个整数，表示网格 $a$。

Output Format

输出一个整数，表示满足条件的路径条数。

Sample

Input1:

3 3 0
6 5 3
5 4 5
7 3 7

Output1:

1

Inout2:

4 5 0
9 9 25 1 9
9 1 9 25 1
9 1 17 9 9
1 1 9 17 25

Output2:

11

Hint

$1 \le n, m \le 20$,$0 \le k \le 10^{18}$,$0 \le a_{i,j} \le 10^{18}$。