{"problem":{"name":"[蓝桥杯 2020 国 B] 质数行者","description":{"content":"游戏在一个 $n \\times m \\times w$ 的立体方格图上进行, 从北到南依次标号为第 $1$ 行到 第 $n$ 行, 从西到东依次标号为第 $1$ 列到第 $m$ 列, 从下到上依次标号为第 $1$ 层到 第 $w$ 层。 小蓝要控制自己的角色从第 $1$ 行第 $1$ 列第 $1$ 层移动到第 $n$ 行第 $m$ 列第 $w$ 层。每一步, 他可以向东走质数格、向南走质数格或者","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8737"},"statements":[{"statement_type":"Markdown","content":"游戏在一个 $n \\times m \\times w$ 的立体方格图上进行, 从北到南依次标号为第 $1$ 行到 第 $n$ 行, 从西到东依次标号为第 $1$ 列到第 $m$ 列, 从下到上依次标号为第 $1$ 层到 第 $w$ 层。\n\n小蓝要控制自己的角色从第 $1$ 行第 $1$ 列第 $1$ 层移动到第 $n$ 行第 $m$ 列第 $w$ 层。每一步, 他可以向东走质数格、向南走质数格或者向上走质数格。每走到 一个位置, 小蓝的角色要稍作停留。\n\n在游戏中有两个陷阱, 分别为第 $r_{1}$ 行第 $c_{1}$ 列第 $h_{1}$ 层和第 $r_{2}$ 行第 $c_{2}$ 列第 $h_{2}$ 层。这两个陷阱的位置可以跨过, 但不能停留。也就是说, 小蓝不能控制角 色某一步正好走到陷阱上，但是某一步中间跨过了陷阱是允许的。\n\n小蓝最近比较清闲, 因此他想用不同的走法来完成这个游戏。所谓两个走法不同, 是指小蓝稍作停留的位置集合不同。\n\n请帮小蓝计算一下，他总共有多少种不同的走法。\n\n提示：请注意内存限制, 如果你的程序运行时超过内存限制将不得分。\n\n## Input\n\n输入第一行包含两个整数 $n, m, w$, 表示方格图的大小。\n\n第二行包含 $6$ 个整数, $r_{1}, c_{1}, h_{1}, r_{2}, c_{2}, h_{2}$ ，表示陷阱的位置。\n\n## Output\n\n输出一行, 包含一个整数, 表示走法的数量。答案可能非常大, 请输出答 案除以 $1000000007$（即 $10^9+7$） 的余数。 \n\n[samples]\n\n## Background\n\n小蓝在玩一个叫质数行者的游戏。\n\n## Note\n\n**【样例说明】**\n\n用 $(r, c, h)$ 表示第 $r$ 行第 $c$ 列第 $h$ 层, 可能的走法有以下几种:\n\n1. $(1,1,1)-(1,3,1)-(1,6,1)-(3,6,1)-(5,6,1)$ 。\n\n2. $(1,1,1)-(1,3,1)-(3,3,1)-(3,6,1)-(5,6,1)$ 。\n\n3. $(1,1,1)-(1,3,1)-(3,3,1)-(5,3,1)-(5,6,1)$ 。\n\n4. $(1,1,1)-(3,1,1)-(3,3,1)-(3,6,1)-(5,6,1)$ 。\n\n5. $(1,1,1)-(3,1,1)-(3,3,1)-(5,3,1)-(5,6,1)$ 。\n\n6. $(1,1,1)-(3,1,1)-(5,1,1)-(5,3,1)-(5,6,1)$ 。\n\n7. $(1,1,1)-(3,1,1)-(5,1,1)-(5,4,1)-(5,6,1)$ 。\n\n8. $(1,1,1)-(1,4,1)-(1,6,1)-(3,6,1)-(5,6,1)$ 。\n\n9. $(1,1,1)-(1,6,1)-(3,6,1)-(5,6,1)$ 。\n\n10. $(1,1,1)-(3,1,1)-(3,6,1)-(5,6,1)$ 。\n\n11. $(1,1,1)-(3,1,1)-(5,1,1)-(5,6,1)$ 。\n\n**【评测用例规模与约定】**\n\n对于 $30 \\%$ 的评测用例 $1 \\leq n, m, w \\leq 50$ 。\n\n对于 $60 \\%$ 的评测用例 $1 \\leq n, m, w \\leq 300$ 。\n\n对于所有评测用例, $1 \\leq n, m, w \\leq 1000,1 \\leq r_{1}, r_{2} \\leq n, 1 \\leq c_{1}, c_{2} \\leq m$, $1 \\leq h_{1}, h_{2} \\leq w$, 陷阱不在起点或终点, 两个陷阱不同。\n\n蓝桥杯 2020 年国赛 B 组 J 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8737","tags":["动态规划 DP","2020","容斥原理","蓝桥杯国赛"],"sample_group":[["5 6 1\n3 4 1 1 2 1","11"]],"created_at":"2026-03-03 11:09:25"}}