Balanced Array

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Hussain really likes playing with arrays. Today he challenged his friend Farah to beat a game he has invented recently.
Hussain will give Farah an array of N positive integers. Farah is allowed to do this move multiple times:
Farah can choose three integers (i , j , k) such that k is a positive integer, 1 ≤ i,j ≤ N, and A[i] is divisible by k. Then she should do the following :
A[i] = A[i] / k
A[j] = A[j] * k
That is, she should multiply A[j] by k, and divide A[i] by k.
Farah must make all the elements of this array equal, by only performing above move, as many times as she wants.
Most of the times, it would be impossible to achieve an array of equal elements. So Farah is allowed to insert at most one element. You can prove that she can always insert an element, so that after the insertion, it becomes possible to make the array elements equal (including the new element), through a series of moves. You have to help Farah find the minimum positive integer that she has to insert into the array so that it's possible for her to make all elements equal after inserting this number.or just tell her that there is no need to insert an additional number.
Input
The first line contains a single integer, N, the number of elements in the array.
The second line contains N positive space separated integers.
Output
In case there is no need to insert an additional number output "justdoit" (without quotations). Otherwise, output the smallest positive integer that Farah must insert into the array. Since this number can be large, you're asked to print the remainder of its division by 10^{9}+7
Constraints
 1 ≤ N ≤ 5000
 1 ≤ A[i] < 10^{9}
Example
Input: 3 4 6 14 Output: 9261
Example 2
Input: 4 25 15 5 27 Output: justdoit
Explanation
In the first Example, after inserting 9261, the array becomes {4, 6, 14, 9261}. We will show a series of moves through which Farah can make the array elements equal. We follow 1based indexing.
 (1, 4, 2). The array becomes {4/2, 6, 14, 9261*2} = {2, 6, 14, 18522}
 (4, 1, 21). The array becomes {2*21, 6, 14, 18522/21} = {42, 6, 14, 882}
 (4, 3, 3). The array becomes {42, 6, 14*3, 882/3} = {42, 6, 42, 294}
 (4, 2, 7). The array becomes {42, 6*7, 42, 294/7} = {42, 42, 42, 42}
There is no smaller positive integer which be inserted to get an equal array. Hence the answer is 9261.
Author:  deadwing97 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/COOK82B 
Tags  cook82, deadwing97, easy, primefactorization, simplemath 
Date Added:  20052017 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions