The First Cube

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
This problem's statement is really a short one.
You are given an integer S. Consider an infinite sequence S, 2S, 3S, ... . Find the first number in this sequence that can be represented as Q^{3}, where Q is some positive integer number. As the sought number could be very large, please print modulo (10^{9} + 7).
The number S will be given to you as a product of N positive integer numbers A_{1}, A_{2}, ..., A_{N}, namely S = A_{1} * A_{2} * ... * A_{N}
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N.
Then there is a line, containing N space separated integers, denoting the numbers A_{1}, A_{2}, ..., A_{N}.
Output
For each test case, output a single line containing the first term of the sequence which is the perfect cube, modulo 10^{9}+7.
Constraints
 1 ≤ T ≤ 10
 (Subtask 1): N = 1, 1 ≤ S ≤ 10^{9}  15 points.
 (Subtask 2): N = 1, 1 ≤ S ≤ 10^{18}  31 point.
 (Subtask 3): 1 ≤ N ≤ 100, 1 ≤ A_{i} ≤ 10^{18}  54 points.
Example
Input: 2 2 2 2 2 2 3 Output: 8 216
Explanation
Example case 1. First few numbers in the infinite sequence 4, 8, 12, 16, 20, , etc. In this sequence, 8 is the first number which is also a cube (as 2^{3} = 8).
Example case 2. First few numbers in the infinite sequence 6, 12, 18, 24, , etc. In this sequence, 216 is the first number which is also a cube (as 6^{3} = 216).
Author:  xcwgf666 
Tester:  furko 
Editorial  http://discuss.codechef.com/problems/FCUBE 
Tags  ltime21, medium, prime, xcwgf666 
Date Added:  24012015 
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, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 