GCD Determinant

We say that a set S = {x_1, x_2, ..., x_n} is factor closed if for any x_i ∈ S and any divisor d of x_i we have d ∈ S. Let's build a GCD matrix (S) = (s_ij), where s_ij = GCD(x_i, x_j) - the greatest common divisor of x_i and x_j. Given the factor closed set S, find the value of the determinant:

Input

The input file contains several test cases. Each test case starts with an integer n (0 < n < 1000), that stands for the cardinality of S. The next line contains the numbers of S: x_1, x_2, ..., x_n. It is known that each x_i is an integer, 0 ≤ x_i ≤ 2·10^9. The input data set is correct and ends with an end of file.

Output

For each test case find and print the value D_n mod 1000000007.

Examples