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 ≤ 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)

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: 2022-12-21 23:32:50

<snip>
[Simes]: Read the footer - Don't post source code here, use the forum.

Last edit: 2022-12-22 13:04:01
syntaxerror029: 2022-05-09 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: 2022-05-09 18:36:05
sankalp_7: 2022-04-15 09:17:59

Nice problem for learning gcd modulo.

mainul3195: 2022-01-19 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: 2022-01-19 08:14:59
kumar_07: 2021-06-14 18:25:41

Please help!!
It's giving me a runtime error on 15th TC.
can anybody help me with this issue???

the_art_maniac: 2021-06-04 11:21:46

great question for gcd , keep in mind the big numbers! :)

ratkill: 2021-05-21 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: 2021-01-09 16:40:24

Finally did it (took 7.13s)
take modulo everywhere you multiply

yaseenmollik: 2020-06-12 06:11:34

It took 7 runtime error to solve this problem finally!

nitishyadav169: 2018-11-22 20:59:15

Help!
On 15 TC it gives NZEC .
I Code in java.
Any Type of Suggestion will be Appreciated.


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