We say that a set \textit{\textbf{S}} = \{\textit{\textbf{x_1}}, \textit{\textbf{x_2}}, ..., \textit{\textbf{x_n}}\} is factor closed if for any \textit{\textbf{x_i}} ∈ \textit{\textbf{S}} and any divisor \textit{\textbf{d}} of \textit{\textbf{x_i}} we have \textit{\textbf{d}} ∈ \textit{\textbf{S}}. Let's build a \textbf{GCD} matrix (\textit{\textbf{S}}) = (\textit{\textbf{s_ij}}), where \textit{\textbf{s_ij}} = \textbf{GCD}(\textit{\textbf{x_i}}\textbf{, }\textit{\textbf{x_j}}) - the greatest common divisor of \textit{\textbf{x_i}} and \textit{\textbf{x_j}}. Given the factor closed set \textit{\textbf{S}}, find the value of the determinant: \includegraphics{https://static.e-olymp.com/content/44/44674662d052bf6c6da94540a13137ec1f0698bf.jpg} \InputFile The input file contains several test cases. Each test case starts with an integer \textit{\textbf{n}} (\textbf{0} < \textit{\textbf{n}} < \textbf{1000}), that stands for the cardinality of \textit{\textbf{S}}. The next line contains the numbers of \textit{\textbf{S}}: \textit{\textbf{x_1}}\textbf{, }\textit{\textbf{x_2}}\textbf{, ..., }\textit{\textbf{x_n}}. It is known that each \textit{\textbf{x_i}} is an integer, \textbf{0} ≤ \textit{\textbf{x}}\textit{_i} ≤ \textbf{2·10^9}. The input data set is correct and ends with an end of file. \OutputFile For each test case find and print the value \textit{\textbf{D_n}} mod \textbf{1000000007}.