НОД определитель

Будем говорить, что множество S = {x_1, x_2, ..., x_n} является фактор-замкнутым, если для любого x_i ∈ S и для любого делителя его делителя d имеет место d ∈ S. Построим GCD матрицу (S) = (s_ij), где s_ij = GCD(x_i, x_j) - наибольший общий делитель x_i и x_j. Зная, что множество S фактор-замкнуто, вычислить значение определителя:

Входные данные

Состоит из нескольких тестов. Каждый тест начинается с целого числа n (0 < n < 1000), равного мощности множества S. Следующая строка содержит числа множества S: x_1, x_2, ..., x_n. Известно, чо каждое x_i является целым, 0 ≤ x_i ≤ 2·10^9. Входные данные корректны и заканчиваются символом конца файла.

Выходные данные

Для каждого теста в отдельной строке вывести значение D_n mod 1000000007.

Примеры