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
fajari5505:
20221221 23:32:50
<snip>


syntaxerror029:
20220509 13:44:33
If you are getting runtime error or WA on test case 15, then you might be storing prime numbers upto sqrt(10^7). You need to store all the prime numbers upto 10^7 since the largest prime factor of the product of all M numbers can be equal to the largest prime number which is <=10^7 Last edit: 20220509 18:36:05 

sankalp_7:
20220415 09:17:59
Nice problem for learning gcd modulo. 

mainul3195:
20220119 08:13:19
Tips: To avoid TLE, use faster factorization method (using smallest prime factor: this method requires logn time complexity instead of sqrt(n) with the help of some precalculations). Last edit: 20220119 08:14:59 

kumar_07:
20210614 18:25:41
Please help!!


the_art_maniac:
20210604 11:21:46
great question for gcd , keep in mind the big numbers! :) 

ratkill:
20210521 16:39:51
@morass : cannot make it work , no matter what i do. The logic seems fine for regular numbers but it doesn't seem to work for big numbers.


wille_25:
20210109 16:40:24
Finally did it (took 7.13s)


yaseenmollik:
20200612 06:11:34
It took 7 runtime error to solve this problem finally! 

nitishyadav169:
20181122 20:59:15
Help!

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