Ada the Ladybug got interesting homework. She had to count gcd of a few numbers. As she is a great mathematician, she done it in meanwhile (in fact, she submited it during the class it was assigned in). The teacher was impressed so he gave Ada a bonus homework (for bonus points). It is same as previous one with a little difference - there are bigger numbers.

Since the number are too large to be written as numbers, they are written as product of lesser numbers. Find their gcd.

Input

The first line of input consists of 2 ≤ N ≤ 10⁶, the number of numbers for which Ada wants to find their gcd.

Each of the next N lines contains an integer 1 ≤ M_i < 10⁶ followed by M_i integers, 1 ≤ A_j ≤ 10⁷, the numbers whose product is the i^th number.

The sum of all M_i won't exceed 10⁶

Output

Print the gcd on a single line. Since this number might be pretty big, output it modulo 10⁹+7 (1000000007)

Example Input 1

3
4 1 2 3 4
1 36
2 6 5

Example Output 1

6

Example Input 2

2
11 1 2 3 4 5 6 7 8 9 10 11
2 1024 15 

Example Output 2

3840