MSE08H  GCD Determinant
English  Vietnamese 
We say that a set S = {x1, x2, …, xn} is factor closed if for any xi ∈ S and any divisor d of xi we have d ∈ S. Let’s build a GCD matrix (S) = (sij), where sij = GCD(xi, xj) – the greatest common divisor of xi and xj. 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: x1, x2, …, xn. It is known that each xi is an integer, 0 < xi < 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 Dn mod 1000000007.
Sample
Input : 2 1 2 3 1 3 9 4 1 2 3 6 Ouput: 1 12 4
hide comments
Arunothia:
20140815 08:48:18
I am getting WA.. have checked my solution several times.. and all my answers seem to match with the admin's solution from Spojtoolkit.. can someone give me some more test cases for me to verify?? 

Ravi Kiran:
20100415 08:38:06
The given array need not be in sorted order!


~!(*(@*!@^&:
20090417 18:25:04
This problem comes from : History of the theory of Number (1st)  see DETER  Knuth (2st). Last edit: 20090414 05:59:34 
Added by:  ~!(*(@*!@^& 
Date:  20090410 
Time limit:  0.129s0.339s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Southeastern European 2008 