Beidajie (North Street) is a very common street name in China. Some famous examples include Beidajie in Shanghai, Xi'an, Chengdu, Taiyuan, and Zhongguancun.

We all know that "Bei" (North) implies freedom and democracy, and "Da" (Big/Great) implies inclusiveness. Therefore, the people living on Beidajie have diverse personalities. Suppose there are $n$ people living on Beidajie.

Someone asked these $n$ people $n-1$ questions, such as:

"Do you use chopsticks?"

"Do you eat braised pork?"

"Do you use tabs or spaces for coding?"

"Do you put curly braces on a new line?"

"..."

Based on each person's answers, they are assigned an $(n-1)$-dimensional binary coordinate, which is a point. Thus, these $n$ points can form a convex hull in an $(n-1)$-dimensional space.

The residents of Beidajie believe that everything inside this polytope is "Huaxia" (China), and everything outside the polytope is "barbarian." It is easy for us to calculate the generalized volume of the Huaxia part.

One day, Mr. B from Qinghualu (Tsinghua Road) came to visit Beidajie. He heard this story and found it interesting, so he also tried to provide answers to these $n-1$ questions.

Mr. B from Qinghualu certainly believes he belongs to Huaxia, but the residents of Beidajie say that if there are $n+1$ points in an $(n-1)$-dimensional space, the volume of the Huaxia part is difficult to calculate.

The atmosphere suddenly became tense. So, this problem is left to you: given $n+1$ points in an $(n-1)$-dimensional space, find the volume of their generalized convex hull.

Since this volume may not be an integer, you only need to output the volume multiplied by $(n-1)!$, modulo $1000000007$.

Input

Read data from standard input.

The first line contains an integer $t$, representing the number of test cases. The following are $t$ test cases.

The first line of each test case is an integer $n$.

The next $n+1$ lines each contain $n-1$ integers, representing a point in $(n-1)$-dimensional space.

Output

Output to standard output.

For each test case, output one integer per line representing the answer.

The result is the volume of the convex hull of the $n+1$ points multiplied by $(n-1)!$, modulo $1000000007$.

Examples

Input 1

1
3
0 0
0 1
1 0
1 1

Output 1

2

Subtasks

$1 \leq t \leq 100$

$3 \leq n \leq 35$

The coordinates of the points are always $0$ or $1$.