#arc083d. [arc083_d]Collecting Balls
[arc083_d]Collecting Balls
题目描述
在 平面上有 个球。它们的坐标分别为 。这里, 和 对于所有 都是介于 到 (包含)的整数,并且没有两个球占据相同的坐标。
为了收集这些球,Snuke 准备了 个机器人,其中 个是 A 型机器人, 个是 B 型机器人。然后,他将类型 A 的机器人放置在坐标 处,将类型 B 的机器人放置在坐标 处,每个位置放置一个。
激活时,每种类型的机器人会按照以下方式运行。
-
当一个类型 A 的机器人在坐标 处被激活时,它会移动到线段 上最低 坐标的球所在的位置,收集该球并停止工作。如果没有这样的球,它将不做任何操作而停止工作。
-
当一个类型 B 的机器人在坐标 处被激活时,它会移动到线段 上最低 坐标的球所在的位置,收集该球并停止工作。如果没有这样的球,它将不做任何操作而停止工作。
一旦停止工作,机器人就不能再次被激活。而且,在一个机器人正在工作时,不能激活新的机器人,直到该机器人停止工作。
当 Snuke 准备激活一个机器人时,他注意到,根据机器人激活的顺序,他可能无法收集到所有的球。
在 种可能的机器人激活顺序中,找出满足所有球都能够被收集的顺序的数量,对 取模。
约束条件
- 若 ,则要么 ,要么 。
输入格式
输入以以下格式从标准输入给出:
...
输出格式
输出满足所有球都能够被收集的机器人激活顺序的数量,对 取模。
示例输入1
示例输出1
我们将放置在 和 处的机器人分别称为 A1 和 A2,将放置在 和 处的机器人分别称为 B1 和 B2。有八种满足条件的激活顺序,如下所示:
- A1, B1, A2, B2
- A1, B1, B2, A2
- A1, B2, B1, A2
- A2, B1, A1, B2
- B1, A1, B2, A2
- B1, A1, A2, B2
- B1, A2, A1, B2
- B2, A1, B1, A2
因此,输出应为 。
示例输入2
示例输出2
示例输入3
示例输出3
示例输入4
示例输出4
示例输入5
示例输出5
当没有满足条件的激活顺序时,输出应为 。