eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Вася недавно изучил определители и теперь хочет применить их в области теории чисел. Он составил матрицу n×n, в которой в i-ой строке на месте j стоит число НОД(i, j). Например, при n = 3 получим определитель:

Теперь Васе нужно вычислить значение определителя этой матрицы, но эта задача оказалась ему не под силу, и теперь Вы должны решить её. Так как определитель может получиться достаточно большим, Вася просит посчитать его по модулю 500009.

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

В первой строке входного файла содержится количество тестов t (1t100000). Каждая последующая строка содержит число n – порядок определителя (1n10^9).

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

Для каждого теста выведите значение соответствующего определителя по модулю 500009.

Пример

Входные данные #1
3
2
3
5
Выходные данные #1
1
2
16
Автор Евгений Служаев