НОД визначник

Множина S = {x_1, x_2, ..., x_n} називається фактор-замкнутою, якщо для будь-якого елемента x_i з S, всі його дільники також належать 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 в окремому рядку.

Приклади