#P10142. [USACO24JAN] Mooball Teams III P
[USACO24JAN] Mooball Teams III P
题目描述
Farmer John 在他的农场上有 头牛(),编号为 。奶牛 位于整数坐标 ()。Farmer John 想要挑选两支队伍来玩哞球游戏!
其中一支队伍将是「红队」;另一队将是「蓝队」。对组队只有很少的要求。两队都不能为空,并且 头奶牛中的每一头至多只能在一个队中(可以两队都不在)。唯一的其他要求是基于哞球独特的特点:一个无限长的网,必须将其放置为平面中非整数坐标的水平或垂直直线,例如 。FJ 挑选队伍必须使得可以用网将两队分开。奶牛们不愿意为此进行移动。
帮帮农夫吧!为 Farmer John 计算选择满足上述要求的红队和蓝队的方法数,对 取模。
输入格式
输入的第一行包含一个整数 。
以下 行每行包含两个空格分隔的整数 和 。输入保证 组成 的一个排列, 类似。
输出格式
输出一个整数,为选择满足上述要求的红队和蓝队的方法数,对 取模。
提示
样例解释 1
我们可以选择红队为牛 1,蓝队为牛 2,或者相反。无论哪种情况,我们都可以用一个网将两支球队分开(例如,)。
样例解释 2
以下是所有的十种可能的将奶牛分队的方法;第 个字符表示第 头奶牛的队伍,R
表示红队,B
表示蓝队,或 .
表示第 头奶牛不在一个队伍中。
样例解释 3
以下是所有的十二种可能的将奶牛分队的方法:
样例解释 4
确保输出答案对 取模。
测试点性质
- 测试点 :。
- 测试点 :。
- 测试点 :。
- 测试点 :没有额外限制。