#arc124f. [arc124_f]Chance Meeting
[arc124_f]Chance Meeting
题目描述
给定一个 行 列的网格。 表示位于从上往下数第 行、从左往右数第 列的方格。
最初,一只骆驼位于 ,一只猫位于 。
你可以发送以下四种指令:
R
:将位于 的骆驼移动到 。D
:将位于 的骆驼移动到 。r
:将位于 的猫移动到 。u
:将位于 的猫移动到 。
满足以下四个条件的指令序列被称为“好”序列。计算好序列的数量,对 取模。
- 骆驼的最终位置为 。
- 猫的最终位置为 。
- 在处理完一条指令后,骆驼和猫在同一个方格上仅发生一次。
- 无论是骆驼还是猫都不会离开网格。
约束条件
- 输入中的所有值均为整数。
输入
输入以以下格式从标准输入中给出:
输出
打印好序列的数量,对 取模。
示例输入 1
2 2
示例输出 1
16
- 好序列包括
DRur
、DurR
、RruD
、RDru
,但不包括DRru
、RRR
。
示例输入 2
200000 200000
示例输出 2
412709667
- 请确保对 取模后再打印结果。