Xiao Hezhou is a good friend of Xiao Qingyu and a member of the famous performing arts group All the Way to the Left. Recently, he has been practicing his ability to identify directions on stage. To practice, he has selected $n$ distinct points $A_1, A_2, \cdots, A_n$ on the stage. The stage is represented as a two-dimensional Cartesian plane, where the $i$-th point is located at coordinates $(x_i, y_i)$. Xiao Hezhou's goal is to traverse all these points in the order $p_1, p_2, \cdots, p_n$. A traversal is a permutation $p$ of length $n$, where each point $A_{p_i}$ is connected to $A_{p_{i+1}}$ by a directed line segment.

Xiao Hezhou considers a traversal to be good if and only if the following conditions are met:

• It is non-self-intersecting. That is, apart from adjacent line segments intersecting at their common endpoint, no other intersections occur.
• The polyline only turns left or goes straight. That is, for all $1\leq i \leq n-2$, the cross product of $\overrightarrow{A_{p_i}A_{p_{i+1}}}$ and $\overrightarrow{A_{p_{i+1}}A_{p_{i+2}}}$ is non-negative.

Xiao Hezhou wants to know the number of good traversals modulo $(10^9 + 7)$. However, he needs to slack off with Xiao Qingyu and cannot solve this challenge himself. Please help him calculate it!

Input

The first line contains a positive integer $T$ ($1\leq T \leq 10^4$), representing the number of test cases.

For each test case, the first line contains an integer $n$ ($1 \leq n \leq 2 \times 10^3$).

The next $n$ lines each contain two integers $x_i$ and $y_i$ ($1 \leq x_i, y_i \leq 10^9$), representing the coordinates of $A_i$. It is guaranteed that all points have distinct coordinates.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $4 \times 10^6$.

Output

For each test case, output a single line containing the number of valid polylines modulo $(10^9 + 7)$.

Examples

Input 1

15
1
1 1
2
1 1
1 2
3
1 1
1 2
1 3
3
1 1
1 2
2 2
5
1 1
1 3
2 2
3 1
3 3
6
1 1
1 3
2 2
3 2
4 1
4 3
6
1 3
2 1
2 2
2 3
2 4
3 2
6
1 1
5 1
3 5
2 2
4 2
3 3
7
1 1
5 1
2 2
3 2
4 2
3 3
3 4
6
2 10
8 9
2 3
2 5
3 5
2 6
10
1 10
7 6
8 4
3 8
6 9
3 7
6 8
8 5
10 9
8 8
8
1 1
2 3
2 4
1 6
5 3
5 4
6 1
6 6
8
1 1
2 3
3 3
4 2
4 4
5 1
1 5
5 5
5
1 1
2 999999998
2 999999999
2 1000000000
3 1
6
1 1
1 1000000000
1000000000 1
1000000000 1000000000
999999999 999999998
999999998 999999997

Output 1

1
2
2
3
8
14
12
16
22
10
54
32
28
10
14

Subtasks

Subtask 1 (7 points)

No additional constraints.