1554. Multiplicative functions
Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ

В теории чисел, мультипликативная функция - это арифметическая функция F(n) от положительного целого n со свойством, что F(1) = 1 и для любых взаимно простых a и b(gcd(a, b) = 1) выполняется F(ab) = F(a)F(b).
Функция E(n) определяемая как E(n) = 1 если n = 1 и = 0 if n > 1, иногда называется единичной функцией для свертки Дирихле.
Если F и G - мультипликативные функции, то можно определить  F * G, то есть свертку Дирихле функций F и G, как

                                                                                                           (сумма в условии задачи)

где суммирование производится по всем положительным делителям d числа n. При помощи этой операции набор мультипликативных функций превращается в группу Абеля; E - идентификационный элемент.
из Википедии.

В этой задаче вы должны найти инверсию мультипликативной функции. Чтобы избежать переполнения определим арифметическую функцию как: F: N —> Z2007 где N набор положительных целых, а Z2007 есть остаточное кольцо (кольцо чисел 0–2006, где операции + и × выполняются по модулю 2007). Функция G называется инверсной для F тогда и только тогда, когда F * G = G * F = E.
Дано первые N значений функции F, найти первые N значений функции G.

Исходные данные
В первой строке число N (1 ≤ N ≤ 10^4). Во второй значения F(1), F(2), F(3), …, F(N), разделенные пробелами. (Each value is nonnegative and doesn't exceed 2006.)
Результат
Вывести N чисел G(1)....G(N)