ADAGCD  Ada and GCD
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^{6}, 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^{6} followed by M_{i} integers, 1 ≤ A_{j} ≤ 10^{7}, the numbers whose product is the i^{th} number.
The sum of all M_{i} won't exceed 10^{6}
Output
Print the gcd on a single line. Since this number might be pretty big, output it modulo 10^{9}+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
hide comments
nitishyadav169:
20181122 20:59:15
Help!


hodobox:
20170727 22:19:01
easier version is http://www.spoj.com/problems/HG/


shubham:
20170609 11:05:59
AC in one go.. :) 

shubham:
20170609 11:05:37
AC in one go.. :) 

pvsmpraveen:
20170414 13:08:17
@morass : can you check my solution? *_*


morass:
20170411 22:26:47
@candide: Good day to you


candide:
20170411 13:06:46
Bad description problem. Introduction characters (Ada, his teacher, etc) is only noise and doesn't help question understanding.


morass:
20170226 12:11:20
@[Lakshman]: Good day to you. Well in fact on every line there is a "big" number, which is product of the numbers on the line and you are supposed to find their gcd.


[Lakshman]:
20170226 09:45:32
I am not getting this problem, can you please explain the sample test cases. 

morass:
20170222 11:13:10
@Vipul Srivastava:: Hello, well there is just one testcase .. so you meant overall complexity? It is slightly complicated (since it is bound to prime arithmetic). Since I'm not a good mathematician I can tell you only STRONG BOUND which is O(Nlog(Ai)log(sqrt(N))) .. but both the logarithms are "weak" (if I can call it this way)

Added by:  Morass 
Date:  20170211 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 