{"problem":{"name":"机器人","description":{"content":"真寻连清理炸弹都懒得自己使用，于是美波里又发明了一款全自动扫地机器人来清理房间。 真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。美波里的机器人每天会从房间的左上角出发，每次随机往右或往下走一步。 若机器人在没有撞墙的情况下走到了右下角，那么它会返回**它经过的所有方砖的灰尘数量的异或和**给美波里；若机器人在走到右下角之前","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10267"},"statements":[{"statement_type":"Markdown","content":"真寻连清理炸弹都懒得自己使用，于是美波里又发明了一款全自动扫地机器人来清理房间。\n\n真寻的房间由 $n$ 行 $m$ 列的方砖组成，第 $i$ 行第 $j$ 列的方砖上的灰尘数量为 $a_{i,j}$。美波里的机器人每天会从房间的左上角出发，每次随机往右或往下走一步。\n\n若机器人在没有撞墙的情况下走到了右下角，那么它会返回**它经过的所有方砖的灰尘数量的异或和**给美波里；若机器人在走到右下角之前撞了墙，即某一步的目标位置不存在，那么机器人会返回一个错误值 $x$ 并结束移动。\n\n现给出某一天真寻的房间中每一块方砖上的灰尘数量，请你求出机器人返回值的期望值。\n\n形式化地，给定一 $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$；求返回值的期望值。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n第一行三个整数 $n,m,x$，分别表示方砖行数、列数及错误值；\n\n接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数表示 $a_{i,j}$，描述每一块方砖上的灰尘数量。\n\n## Output\n\n一行一个整数 $ans$，表示期望值在模 $10^9+7$ 意义下的值。\n\n若对有理数取余有疑惑，请参照 [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613)。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/sub3kd3c.png)\n\n> 画师：白森 さわ（from pixiv），侵删。\n\n## Note\n\n**样例** $\\mathbf{1}$ **解释**\n\n若机器人第一步往下走，则：\n\n- 若机器人第二步往下走，则撞墙，返回 $5$，概率为 $\\frac{1}{4}$；\n\n- 若机器人第二步往右走，则：\n\n\t- 若机器人第三步往下走，则撞墙，返回 $5$，概率为 $\\frac{1}{8}$；\n    \n    - 若机器人第三步往右走，则到达右下角，返回 $7\\oplus 10\\oplus 6\\oplus 3=8$，概率为 $\\frac{1}{8}$；\n    \n若机器人第一步往右走，则：\n\n- 若机器人第二步往下走，则：\n\n\t- 若机器人第三步往下走，则撞墙，返回 $5$，概率为 $\\frac{1}{8}$；\n    \n    - 若机器人第三步往右走，则到达右下角，返回 $7\\oplus 18\\oplus 6\\oplus 3=16$，概率为 $\\frac{1}{8}$；\n    \n- 若机器人第二步往右走，则：\n    \n    - 若机器人第三步往下走，则到达右下角，返回 $7\\oplus 18\\oplus 4\\oplus 3=18$，概率为 $\\frac{1}{8}$；\n    \n    - 若机器人第三步往右走，则撞墙，返回 $5$，概率为 $\\frac{1}{8}$；\n\n因此，返回值的期望值为 $\\frac{3\\times 5+8+16+18}{8}+\\frac{5}{4}=\\frac{67}{8}$，在模 $10^9+7$ 意义下为 $375000011$。\n\n**数据范围**\n\n对于所有数据，$1\\leq n,m\\leq 10^3$，$0\\leq a_{i,j},x\\leq 10^9$。\n\n本题共 $22$ 个测试点，**采用捆绑测试**，子任务及数据点分配如下：\n\n| 子任务编号 | 数据点编号 | 特殊性质 | 分值 |\n| :-: | :-: | :-: | :-: |\n| $0$ | $1\\sim 4$ | $n,m\\leq 12$ | $10$ |\n| $1$ | $5\\sim 8$ | $n,m\\leq 20$ | $20$ |\n| $2$ | $9\\sim 12$ | $a_{i,j}\\leq 20$ | $20$ |\n| $3$ | $13\\sim 16$ | $x=0$ | $20$ |\n| $4$ | $17\\sim 22$ | 无特殊限制 | $30$ |\n\n**提示**\n\n$\\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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10267","tags":["动态规划 DP","数学"],"sample_group":[["2 3 5\n7 18 4\n10 6 3","375000011"],["6 5 0\n9 4 6 2 3\n6 4 4 0 1\n2 0 4 3 0\n1 5 7 3 4\n5 0 2 1 5\n6 4 9 8 3","99609378"]],"created_at":"2026-03-03 11:09:25"}}