{"problem":{"name":"[USACO24JAN] Mooball Teams III P","description":{"content":"Farmer John 在他的农场上有 $N$ 头牛（$2\\le N\\le 2\\cdot 10^5$），编号为 $1\\ldots N$。奶牛 $i$ 位于整数坐标 $(x_i,y_i)$（$1\\le x_i,y_i\\le N$）。Farmer John 想要挑选两支队伍来玩哞球游戏！ 其中一支队伍将是「红队」；另一队将是「蓝队」。对组队只有很少的要求。两队都不能为空，并且 $N$ 头奶牛中的每一","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10142"},"statements":[{"statement_type":"Markdown","content":"Farmer John 在他的农场上有 $N$ 头牛（$2\\le N\\le 2\\cdot 10^5$），编号为 $1\\ldots N$。奶牛 $i$ 位于整数坐标 $(x_i,y_i)$（$1\\le x_i,y_i\\le N$）。Farmer John 想要挑选两支队伍来玩哞球游戏！\n\n其中一支队伍将是「红队」；另一队将是「蓝队」。对组队只有很少的要求。两队都不能为空，并且 $N$ 头奶牛中的每一头至多只能在一个队中（可以两队都不在）。唯一的其他要求是基于哞球独特的特点：一个无限长的网，必须将其放置为平面中非整数坐标的水平或垂直直线，例如 $x=0.5$。FJ 挑选队伍必须使得可以用网将两队分开。奶牛们不愿意为此进行移动。\n\n帮帮农夫吧！为 Farmer John 计算选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。\n\n## Input\n\n输入的第一行包含一个整数 $N$。\n\n以下 $N$ 行每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。输入保证 $x_i$ 组成 $1\\ldots N$ 的一个排列，$y_i$ 类似。\n\n## Output\n\n输出一个整数，为选择满足上述要求的红队和蓝队的方法数，对 $10^9+7$ 取模。\n\n[samples]\n\n## Note\n\n### 样例解释 1\n\n我们可以选择红队为牛 1，蓝队为牛 2，或者相反。无论哪种情况，我们都可以用一个网将两支球队分开（例如，$x=1.5$）。\n\n### 样例解释 2\n\n以下是所有的十种可能的将奶牛分队的方法；第 $i$ 个字符表示第 $i$ 头奶牛的队伍，`R` 表示红队，`B` 表示蓝队，或 `.` 表示第 $i$ 头奶牛不在一个队伍中。 \n\n```plain\nRRB\nR.B\nRB.\nRBB\n.RB\n.BR\nBRR\nBR.\nB.R\nBBR\n```\n\n### 样例解释 3\n\n以下是所有的十二种可能的将奶牛分队的方法：\n\n```plain\nRRB\nR.B\nRBR\nRB.\nRBB\n.RB\n.BR\nBRR\nBR.\nBRB\nB.R\nBBR\n```\n\n### 样例解释 4\n\n确保输出答案对 $10^9+7$ 取模。\n\n### 测试点性质\n\n- 测试点 $5$：$N\\le 10$。\n- 测试点 $6-9$：$N\\le 200$。\n- 测试点 $10-13$：$N\\le 3000$。\n- 测试点 $14-24$：没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10142","tags":["线段树","USACO","2024","容斥原理"],"sample_group":[["2\n1 2\n2 1","2"],["3\n1 1\n2 2\n3 3","10"],["3\n1 1\n2 3\n3 2","12"],["40\n1 1\n2 2\n3 3\n4 4\n5 5\n6 6\n7 7\n8 8\n9 9\n10 10\n11 11\n12 12\n13 13\n14 14\n15 15\n16 16\n17 17\n18 18\n19 19\n20 20\n21 21\n22 22\n23 23\n24 24\n25 25\n26 26\n27 27\n28 28\n29 29\n30 30\n31 31\n32 32\n33 33\n34 34\n35 35\n36 36\n37 37\n38 38\n39 39\n40 40","441563023"]],"created_at":"2026-03-03 11:09:25"}}