{"problem":{"name":"【MX-X1-T2】「KDOI-05」简单的有限网格问题","description":{"content":"小 S 在玩一款小游戏。游戏中会有一个 $n\\times m$ 的棋盘，其中 $k$ 个位置上有星星。初始有一个捕捉器，在 $(x,y)$ 位置。每次操作，你可以将捕捉器移动到同行或同列的某个位置，使得新位置与原位置不同且必须保证新位置 $(x',y')$ 满足 $1\\leq x'\\leq n$，$1\\leq y'\\leq m$。**捕捉器会捕捉 $(x,y)$ 到 $(x',y')$ 路径上所有","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10714"},"statements":[{"statement_type":"Markdown","content":"小 S 在玩一款小游戏。游戏中会有一个 $n\\times m$ 的棋盘，其中 $k$ 个位置上有星星。初始有一个捕捉器，在 $(x,y)$ 位置。每次操作，你可以将捕捉器移动到同行或同列的某个位置，使得新位置与原位置不同且必须保证新位置 $(x',y')$ 满足 $1\\leq x'\\leq n$，$1\\leq y'\\leq m$。**捕捉器会捕捉 $(x,y)$ 到 $(x',y')$ 路径上所有的星星**。一个星星被捕捉后将会消失。\n\n游戏的目标是在恰好两步内获得尽可能多的星星，然而小 S 不会玩，于是每次就会随意挑选一个可以移动到的新位置进行移动。对于 $(n+m-2)^2$ 种小 S 的不同移动方案，求捕捉到的星星数量之和，答案对 $10^9+7$ 取模。\n\n## Input\n\n第一行三个正整数 $n,m,k$，表示棋盘大小与星星个数。\n\n第二行两个正整数 $x,y$，表示捕捉器初始位置。\n\n接下来 $k$ 行，每行两个正整数，表示每颗星星所在的位置 $(p,q)$。每个位置上可以有多颗星星。\n\n## Output\n\n一行，一个非负整数，表示对于 $(n+m-2)^2$ 种小 S 的不同移动方案，他能捕捉到的星星数量之和，对 $10^9+7$ 取模。\n\n[samples]\n\n## Background\n\n原题链接：<https://oier.team/problems/X1B>。\n\n## Note\n\n**【样例解释 \\#1】**\n\n网格图中，一种合法的移动捕捉器的方案是：\n\n$$(2,2)\\to(1,2)\\to(1,3)$$\n\n在该方案中，可以捕捉到位置在 $(1,2)$ 和 $(1,3)$ 的各 $1$ 颗星星。\n\n**【数据范围】**\n\n**本题采用捆绑测试。**\n\n| 子任务编号 | 分值 | $n\\leq$ | $m\\leq$ |\n|:--:|:--:|:--:|:--:|\n| $1$ | $5$ | $50$ | $50$ |\n| $2$ | $10$ | $1000$ | $1000$ |\n| $3$ | $20$ | $10^5$ | $10^5$ |\n| $4$ | $25$ | $10^5$ | $10^9$ |\n| $5$ | $25$ | $10^9$ | $10^9$ |\n| $6$ | $15$ | $10^{18}$ | $10^{18}$ |\n\n对于 $100\\%$ 的数据，$1\\leq k\\leq10^5$，$1\\leq n,m\\leq10^{18}$，$1\\leq x,p\\leq n$，$1\\leq y,q\\leq m$，$(x,y)\\neq(p,q)$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10714","tags":["数学","O2优化","分类讨论","梦熊比赛"],"sample_group":[["3 3 4\n2 2\n1 1\n1 2\n1 3\n3 1\n","11"],["5 8 9\n2 7\n1 7\n2 2\n4 7\n4 5\n4 7\n2 8\n5 2\n1 7\n1 7","153"]],"created_at":"2026-03-03 11:09:25"}}