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

读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE。

输入：xorpath.in

输出：xorpath.out

题目描述

给定一个 $n\times m$ 的网格，格子 $(i,j)$ 上有一个非负整数 $a_{i,j}$。

你需要统计从左上角 $(1,1)$ 走到右下角 $(n,m)$ 的路径条数，要求：

• 每一步只能向右或向下移动；
• 路径上所有经过格子的数字按位异或（xor）后的结果恰好等于 $k$。

请输出满足条件的路径总数。

输入格式

第一行三个整数 $n,m,k$（$1 \le n,m \le 20,\ 0 \le k \le 10^{18}$）。

接下来 $n$ 行，每行 $m$ 个整数，表示网格数组 $a$，其中 $0 \le a_{i,j} \le 10^{18}$。

输出格式

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

输入输出样例

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

3

说明/提示

样例中满足条件的 3 条路径分别为：

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