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 ≤ 106, the number of numbers for which Ada wants to find their gcd.

Each of the next N lines contains an integer 1 ≤ Mi < 106 followed by Mi integers, 1 ≤ Aj ≤ 107, the numbers whose product is the ith number.

The sum of all Mi won't exceed 106

### Output

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

```3
4 1 2 3 4
1 36
2 6 5
```

```6
```

### Example Input 2

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

```3840
```