GCD Determinant#1373
We say that a set S = \{x_1, x_2, \ldots, x_n\} is factor-closed if for any x_i \in S and any divisor of x_i, we have d \in S. Construct the GCD matrix (S) = (s_{ij}), where s_{ij} = \operatorname{GCD}(x_i, x_j) is the greatest common divisor of x_i and x_j. Given that the set is factor-closed, compute the value of the determinant:
The input consists of several test cases. Each test case starts with an integer (0 < n < 1000), representing the cardinality of . The next line contains the elements of : x_1, x_2, \ldots, x_n. Each x_i is an integer, 0 \le x_i \le 2 \cdot 10^9. The input is correct and ends with the end of file.
For each test case, output the value of D_n \bmod 1000000007 on a separate line.
Example 1