机器人

 > 画师：白森 さわ（from pixiv），侵删。

真寻连清理炸弹都懒得自己使用，于是美波里又发明了一款全自动扫地机器人来清理房间。 真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。美波里的机器人每天会从房间的左上角出发，每次随机往右或往下走一步。 若机器人在没有撞墙的情况下走到了右下角，那么它会返回**它经过的所有方砖的灰尘数量的异或和**给美波里；若机器人在走到右下角之前撞了墙，即某一步的目标位置不存在，那么机器人会返回一个错误值 $x$ 并结束移动。 现给出某一天真寻的房间中每一块方砖上的灰尘数量，请你求出机器人返回值的期望值。 形式化地，给定一 $n\times m$ 的矩阵 $a$，第 $i$ 行第 $j$ 列的权值为 $a_{i,j}$，现有一机器人从 $(1,1)$ 出发，每次各有 $\frac{1}{2}$ 的概率从 $(i,j)$ 移动至 $(i,j+1)$ 或 $(i+1,j)$；若机器人移动至 $(n,m)$，则返回**路径点权异或和**；若在移动至 $(n,m)$ 前有任意时刻移动至矩阵外，则返回 $x$；求返回值的期望值。 答案对 $10^9+7$ 取模。

第一行三个整数 $n,m,x$，分别表示方砖行数、列数及错误值； 接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $a_{i,j}$，描述每一块方砖上的灰尘数量。

一行一个整数 $ans$，表示期望值在模 $10^9+7$ 意义下的值。 若对有理数取余有疑惑，请参照 [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。

2 3 5
7 18 4
10 6 3

375000011

6 5 0
9 4 6 2 3
6 4 4 0 1
2 0 4 3 0
1 5 7 3 4
5 0 2 1 5
6 4 9 8 3

99609378

**样例** $\mathbf{1}$ **解释** 若机器人第一步往下走，则： - 若机器人第二步往下走，则撞墙，返回 $5$，概率为 $\frac{1}{4}$； - 若机器人第二步往右走，则： - 若机器人第三步往下走，则撞墙，返回 $5$，概率为 $\frac{1}{8}$； - 若机器人第三步往右走，则到达右下角，返回 $7\oplus 10\oplus 6\oplus 3=8$，概率为 $\frac{1}{8}$； 若机器人第一步往右走，则： - 若机器人第二步往下走，则： - 若机器人第三步往下走，则撞墙，返回 $5$，概率为 $\frac{1}{8}$； - 若机器人第三步往右走，则到达右下角，返回 $7\oplus 18\oplus 6\oplus 3=16$，概率为 $\frac{1}{8}$； - 若机器人第二步往右走，则： - 若机器人第三步往下走，则到达右下角，返回 $7\oplus 18\oplus 4\oplus 3=18$，概率为 $\frac{1}{8}$； - 若机器人第三步往右走，则撞墙，返回 $5$，概率为 $\frac{1}{8}$； 因此，返回值的期望值为 $\frac{3\times 5+8+16+18}{8}+\frac{5}{4}=\frac{67}{8}$，在模 $10^9+7$ 意义下为 $375000011$。 **数据范围** 对于所有数据，$1\leq n,m\leq 10^3$，$0\leq a_{i,j},x\leq 10^9$。 本题共 $22$ 个测试点，**采用捆绑测试**，子任务及数据点分配如下： | 子任务编号 | 数据点编号 | 特殊性质 | 分值 | | :-: | :-: | :-: | :-: | | $0$ | $1\sim 4$ | $n,m\leq 12$ | $10$ | | $1$ | $5\sim 8$ | $n,m\leq 20$ | $20$ | | $2$ | $9\sim 12$ | $a_{i,j}\leq 20$ | $20$ | | $3$ | $13\sim 16$ | $x=0$ | $20$ | | $4$ | $17\sim 22$ | 无特殊限制 | $30$ | **提示** $\oplus$ 表示异或（bitwise xor），$x_1,x_2,x_3,\cdots,x_n$ 的异或和为 $x_1\oplus x_2\oplus x_3\oplus\cdots \oplus x_n$。