#2872. 数数

数数

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

我们称一个集合 S=(x1,y1),(x2,y2),...,(xk,yk)\red{S = {(x_1, y_1), (x_2, y_2), ... , (x_k, y_k)}}是好的,当且仅当把它们按 照 yi\red{y_i }降序排序后满足:

? 对于所有满足 3\red{3 ≤} j\red{j ≤} k\red{k}j\red{j,}xj2<xj<xj1\red{x_{j-2} < x_j < x_{j-1}}或者 xj1<xj<xj2\red{x_{j-1} < x_j < x_{j-2}}。 牛牛在二维平面上有一个 n\red{n}个点的集合。牛牛请你帮他算算有多少个非空子集 S\red{S} 是好的。因为答案可能很大,你只需要告诉他答案对 109+7\red{10^9 + 7 }取模后的结果。

输入格式

第一行一个整数 n\red{n,}表示点的个数。

接下来n\red{n }行,每行两个整数xi,yi\red{x_i, y_i ,}表示第 i\red{i}个点的坐标。

输出格式

输出一行一个整数表示答案对 109+7\red{10^9 + 7 }取模后的结果。

样例

输入样例1

4
2 2
3 1
1 4
4 3

输出样例1

14

输入样例2

18
270154266 674435265
-54662325 -976053549
-17003000 493156492
-122658950 -64114385
64821512 -139450437
-828383768 483137960
-394435024 313278055
-137780421 898227301
-594159382 558373148
-195146551 476698144
228023360 -71588671
-890522860 -549082338
-188398146 934884255
-490250512 969810007
647554795 -294860080
-242692159 709705437
-150243399 -263691260
762072374 698248401

输出样例2

791

提示

样例 1\red{1 }说明

除了 {(2,2),(3,1),(1,4)}\red{\{(2,2),(3,1),(1,4)\}}以外,其它非空子集均合法。

对于 8%\red{8\% }的数据,有 1\red{1 ≤} n\red{n ≤} 18\red{18}

对于 20%\red{20\% }的数据,有 1\red{1 ≤} n\red{n ≤} 100\red{100}

对于 52%\red{52\% }的数据,有 1\red{1 ≤} n\red{n ≤} 1500\red{1500}

对于 72%\red{72\% }的数据,有 1\red{1 ≤} n\red{n ≤} 4000\red{4000}

对于 100%\red{100\% }的数据,有 1\red{1 ≤} n\red{n ≤} 6000\red{6000,}0xi,yi109\red{0 ≤∣ xi ∣, ∣ yi ∣≤ 10^9}xi\red{x_i}互不相同,yi\red{y_i} 互 不相同

2022CSP—J2模拟赛2

未参加
状态
已结束
规则
OI
题目
4
开始于
2022-10-2 19:30
结束于
2022-10-2 23:00
持续时间
3.5 小时
主持人
参赛人数
50