Будем говорить, что множество \textit{\textbf{S}} = \{\textit{\textbf{x_1}}, \textit{\textbf{x_2}}, ..., \textit{\textbf{x_n}}\} является фактор-замкнутым, если для любого \textit{\textbf{x_i}} ∈ \textit{\textbf{S}} и для любого делителя его делителя \textit{\textbf{d}} имеет место \textit{\textbf{d}} ∈ \textit{\textbf{S}}. Построим \textbf{GCD} матрицу (\textit{\textbf{S}}) = (\textit{\textbf{s_ij}}), где \textit{\textbf{s_ij}} = \textbf{GCD}(\textit{\textbf{x_i}}\textbf{, }\textit{\textbf{x_j}}) - наибольший общий делитель \textit{\textbf{x_i}} и \textit{\textbf{x_j}}. Зная, что множество \textit{\textbf{S}} фактор-замкнуто, вычислить значение определителя: \includegraphics{https://static.e-olymp.com/content/44/44674662d052bf6c6da94540a13137ec1f0698bf.jpg} \InputFile Состоит из нескольких тестов. Каждый тест начинается с целого числа \textit{\textbf{n}} (\textbf{0} < \textit{\textbf{n}} < \textbf{1000}), равного мощности множества \textit{\textbf{S}}. Следующая строка содержит числа множества \textit{\textbf{S}}: \textit{\textbf{x_1}}\textbf{, }\textit{\textbf{x_2}}\textbf{, ..., }\textit{\textbf{x_n}}. Известно, чо каждое \textit{\textbf{x_i}} является целым, \textbf{0} ≤ \textit{\textbf{x}}\textit{_i} ≤ \textbf{2·10^9}. Входные данные корректны и заканчиваются символом конца файла. \OutputFile Для каждого теста в отдельной строке вывести значение \textit{\textbf{D_n}} mod \textbf{1000000007}.