Uolevi manages a restaurant. The menu of the restaurant contains n items. Each of them has some spiciness value p_i and sweetness value w_i. Uolevi knows that each customer has some spiciness and sweetness preference and will order food according to that. More specifically each customer has two positive numbers a and b, and they will order the food i that maximizes a \cdot p_i + b \cdot w_i. If there are multiple items that maximize the value, they will order a random item among them.

Uolevi has noticed that some of the items on the menu are useless, because nobody will never order them. An useless item is an item that will never be ordered no matter what preference the customer has. Uolevi wants to form a new menu that is a subset of current menu such that the menu has no useless items. In how many ways Uolevi can do that? As the answer can be large, output it modulo 1000000007.

Input

The first line of input contains integer n, the size of the current menu. Next n lines each contain p_i and w_i, the spiciness and sweetness values for ith food. If i \neq j, then it holds that p_i \neq p_j or w_i \neq w_j.

Output

Output one integer, the number of different nonempty subsets of the current menu that contain no useless items.

Constraints

• 1 \le n \le 2000
• 1 \le p_i, w_i \le 10^9

Examples

Input:

4
2 2
1 4
3 3
4 1

Output:

10

The allowed subsets are \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 4\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{2, 3, 4\}.

Input:

3
10 40
20 30
30 20

Output:

7

All of the subsets are allowed

Input:

3
1 1
1 3
3 1

Output:

4

Input:

3
1 4
2 2
4 1

Output:

6