题目背景

画师：白森 さわ（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 【模板】有理数取余。

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$
$3$	$13\sim 16$	$x=0$
$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$。