折射

refract.cpp/in/out

• 时间限制：1s
• 内存限制：128MB

题目描述

小 Y 十分喜爱光学相关的问题，一天他正在研究折射。

他在平面上放置了 $n$ 个折射装置，希望利用这些装置画出美丽的折线。折线将从某个装置出发，并且在经过一处装置时可以转向，若经过的装置坐标依次为 $(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$，则必须满足：

• $\forall j \in (1, k],\ y_j < y_{j-1}$
• $\forall j \in (2, k],\ x_{j-2} < x_j < x_{j-1}$ 或 $x_{j-1} < x_j < x_{j-2}$

现在他希望你能告诉他，一共有多少种不同的光线能被他画出来，两种光线不同当且仅当经过的折射装置的集合不同。你只需要告诉他答案对 $10^9 + 7$ 取模后的结果。

输入格式

第一行一个正整数 $n$，表示折射装置的数量。

接下来 $n$ 行，每行两个整数 $x_i, y_i$ 表示折射装置的坐标。

输出格式

输出一行一个整数，表示答案对 $10^9 + 7$ 取模后的结果。

样例输入

4
2 2
3 1
1 4
4 3

样例输出

14

数据范围

• 对于 10% 的数据：$n \le 700$，$1 \le x_i, y_i \le N$。
• 对于 20% 的数据：$n \le 1000$，$1 \le x_i, y_i \le N$。
• 对于 50% 的数据：$n \le 4000$，$|x_i|, |y_i| \le 10^9$。
• 对于 100% 的数据：$n \le 6000$，$|x_i|, |y_i| \le 10^9$。
• 所有数据满足 $\forall i \neq j,\ x_i \neq x_j$ 且 $y_i \neq y_j$。