Farmer John 的农场里有 $N$ 头奶牛 ($2 \leq N \leq 2\cdot 10^5$)，编号方便地记为 $1 \dots N$。第 $i$ 头奶牛位于整数坐标 $(x_i, y_i)$ ($1\le x_i,y_i\le N$)。Farmer John 想要挑选两支队伍来进行一场“哞球”比赛！

其中一支队伍为“红队”，另一支为“蓝队”。队伍的组建要求很少：两支队伍都不能为空，且每头奶牛最多只能加入一支队伍（也可以都不加入）。另一个要求源于哞球的一项独特规则：必须在平面上放置一条无限长的网，网必须是一条非整数坐标的水平线或垂直线（例如 $x = 0.5$）。FJ 必须挑选队伍，使得这两支队伍能够被这条网隔开。奶牛们不愿意移动位置来满足这一条件。

请帮帮 Farmer John！计算满足上述要求的挑选红队和蓝队的方法数，结果对 $10^9+7$ 取模。

输入格式

第一行包含一个整数 $N$。

接下来的 $N$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $y_i$。保证 $x_i$ 是 $1\dots N$ 的一个排列，$y_i$ 也是如此。

输出格式

输出一个整数，表示满足上述要求的挑选红队和蓝队的方法数，对 $10^9+7$ 取模。

样例

样例输入 1

2
1 2
2 1

样例输出 1

2

我们可以选择第 1 头奶牛为红队，第 2 头为蓝队，或者反过来。在这两种情况下，我们都可以用网将两支队伍隔开（例如 $x=1.5$）。

样例输入 2

3
1 1
2 2
3 3

样例输出 2

10

这里是所有十种可能的奶牛分组方式；第 $i$ 个字符表示第 $i$ 头奶牛所属的队伍，. 表示第 $i$ 头奶牛未加入任何队伍。

RRB
R.B
RB.
RBB
.RB
.BR
BRR
BR.
B.R
BBR

样例输入 3

3
1 1
2 3
3 2

样例输出 3

12

这里是所有十二种可能的奶牛分组方式：

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

样例输出 4

441563023

请确保输出结果对 $10^9+7$ 取模。

子任务

• 输入 5: $N\le 10$
• 输入 6-9: $N\le 200$
• 输入 10-13: $N\le 3000$
• 输入 14-24: 无额外限制。