给定平面上 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。