#PU1382. USACO 2024 January Contest, Platinum — Problem 3. Mooball Teams III
USACO 2024 January Contest, Platinum — Problem 3. Mooball Teams III
USACO 2024 January Contest, Platinum — Problem 3. Mooball Teams III
题目描述
Farmer John has cows on his farm (), conveniently numbered . Cow is located at integer coordinates (). Farmer John wants to pick two teams for a game of mooball! One of the teams will be the "red" team; the other team will be the "blue" team. There are only a few requirements for the teams. Neither team can be empty, and each of the cows must be on at most one team (possibly neither). The only other requirement is due to a unique feature of mooball: an infinitely long net, which must be placed as either a horizontal or vertical line in the plane at a non-integer coordinate, such as . FJ must pick teams so that it is possible to separate the teams by a net. The cows are unwilling to move to make this true. Help a farmer out! Compute for Farmer John the number of ways to pick a red team and a blue team satisfying the above requirements, modulo .
输入格式
The first line of input contains a single integer The next lines of input each contain two space-separated integers and . It is guaranteed that the form a permutation of , and same for the .
输出格式
A single integer denoting the number of ways to pick a red team and a blue team satisfying the above requirements, modulo .
数据范围
(见题面原文)
样例
样例 1
2
1 2
2 1
2
We can either choose the red team to be cow 1 and the blue team to be cow 2, or
the other way around. In either case, we can separate the two teams by a net
(for example, $x=1.5$).
样例 2
3
1 1
2 2
3 3
10
Here are all ten possible ways to place the cows on teams; the $i$th character
denotes the team of the $i$th cow, or . if the $i$th cow is not on a team.
RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR
样例 3
3
1 1
2 3
3 2
12
Here are all twelve possible ways to place the cows on teams:
RRB
R.B
RBR
RB.
RBB
.RB
.BR
BRR
BR.
BRB
B.R
BBR
样例 4
40
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
441563023
Make sure to output the answer modulo $10^9+7$.