#4393. 集合 (set)

集合 (set)

[丛雨]认为一个集合 S={(x1,y1),(x2,y2),,(xk,yk)}S = \{(x_1 , y_1) , (x_2 , y_2) , … , (x_k,y_k)\} 是好的,当且仅当把它们按照 yiy_i 降序(从大到小)排序后满足:对于所有满足 3jk3 \le j \le kjj ,有 xj2<xj<xj1x_{j−2} \lt x_j \lt x_{j−1} 或者 xj1<xj<xj2x_{j−1} \lt x_j \lt x_{j−2} 。 现在丛雨在二维平面上有一个 nn 个点的集合。丛雨请你帮她算算有多少个非空子集 SS 是好的。因为答案可能很大,你只需要告诉她答案对 10000000071000000007 取模后的结果。

输入格式(set.in)

第一行一个整数 nn ,表示点的个数。 接下来 nn 行,每行两个整数 xix_i , yiy_i ,表示第 ii 个点的坐标。

输出格式(set.out)

一行一个整数表示答案对 10000000071000000007 取模后的结果。

输入样例A

4
2 2
3 1
1 4
4 3

输出样例A

14

输入样例B

75
803964900 -930596723
525164269 -648731976
-533848896 522943765
918541542 148038300
-696361358 410369105
-481914985 593865204
661240436 -158507921
946957524 402545345
-444068215 219906151
-566472782 228953303
-610676034 36263862
427325821 -342445808
-348310755 537233993
945818074 995155058
-74404869 212305185
392225014 -668623367
-460152351 744436609
76834598 -248030661
-534171237 199264256
845777237 -944848027
461879820 426279121
-387307786 -672460715
-603624642 -148143871
-27710410 -31227559
489145540 742630416
597813835 -80994242
-172765183 -766696528
-855341564 -475277401
686846590 -696773078
-212405107 -854325456
-940858724 -297109609
-706591093 921464600
19190445 352976079
271285312 -848315334
-167193621 880292116
196529904 -637567919
-293768257 444808383
-359966203 -33300904
593463820 -669174589
224800853 592562287
92359534 693652381
-480640672 902840301
834675744 722753362
-51883842 -430179373
213273196 -923045750
-370581544 588953125
338409459 -333320574
178338548 856940336
503919808 579896114
49606341 -810016437
-376419617 343129878
-159356211 -188452449
-205245062 -513103005
-548756961 677137347
912743269 586364815
-282481972 -698335759
738320648 -473695868
257191529 740404539
-352182717 -839247811
287509259 607277657
-165794526 -614387292
-360666396 373692523
882928658 236645524
-15583239 990217201
-748009463 -270455053
885200258 -109400804
-628004684 204328197
541831889 523539073
-227975396 -654839280
55774634 -316000701
457875462 -424904185
275167601 -424685923
-45209688 -890057365
-435896579 -307461212
-726904736 -939739183

输出样例B

4949470

数据范围

对于 8%8\% 的数据,满足 1n181 \le n \le 18 。 对于 20%20\% 的数据,满足 1n1001 \le n \le 100 。 对于 52%52\% 的数据,满足 1n15001 \le n \le 1500 。 对于 72%72\% 的数据,满足 1n40001 \le n \le 4000 。 对于 100%100\% 的数据,满足 1n6000,0xi,yi1091 \le n \le 6000, 0 \le |x_i|, |y_i| \le 10^9xix_i 互不相同,yiy_i互不相同。