← 返回题目列表

Codeforces · 870/E

E. 点、线和现成的标题

中文机器翻译题面 查看原题

给定平面上 n 个具有积分坐标的不同点。对于每个点,您可以绘制一条穿过它的垂直线,绘制一条穿过它的水平线,或者不执行任何操作。

您将几条重合的直线视为一条直线。你能得到多少张不同的图片?打印以 109 + 7 为模的答案。

输入

第一行包含单个整数 n (1 ≤ n ≤ 105) — 点数。

n 行如下。这些行的第 (i + 1) 行包含两个整数 xi, yi (- 109 ≤ xi, yi ≤ 109) - 第 i 个点的坐标。

保证所有点都是不同的。

输出

打印可能的不同图片的数量以 109 + 7 为模。

示例

输入 #1

4
1 1
1 2
2 1
2 2

输出 #1

16

输入 #2

2
-1 -1
0 1

输出 #2

9

注意

在第一个示例中,有两条垂直线和两条水平线穿过这些点。您可以使用这些线条的任何子集来获取图片。例如,您可以通过两种方式获取包含所有四行的图片(每个段代表包含它的一行)。

第一种方式: 第二种方式:

在第二个示例中,您可以独立处理两个点。图片数量为 32 = 9。