Aditya is a very brilliant student and mathematics is his favorite subject. On one fine day he was taught functions by his teacher in school, after returning back to home his elder brother gave him a question on functions to test his knowledge. He gave him a list of numbers namely a of size n and two functions namely g(x) and f(x).
- g(x) - GCD of all the elements of the list
- f(x) - Products of all the elements of the list
He asked Aditya to solve (f(x)g(x)) mod (MagicQuotient), where MagicQuotient = 109 + 7.
Since, the problem is too hard for a school going student, he asked you to help him. You being a good friend of Aditya have to solve the problem on his behalf.
Input constraints:
The first line of input will contain an integer — N. The next line will contain N integers denoting the elements of the list.
Output constraints:
Print the required answer of the equation.
Constraints:
1 ≤ N ≤ 50
1 ≤ Ai ≤ 103
Here we can see that the product of the elements of array is 12 and the GCD of the array comes out to be 2 . Thus the answer would be 12^2 which is 144.
