Мала теорема Ферма#3723

Мала теорема Ферма

4 секунди

256 мегабайтів

Складна

Мала теорема Ферма стверджує, що для будь-якого простого числа $p$ і будь-якого цілого числа $a$ вираз $a^{p} - a$ a^p - a ділиться на $p$ . У цій задачі ми досліджуємо схожу концепцію.

Задано натуральне число $n > 1$ n > 1. Ваше завдання — знайти всі натуральні числа $m$ такі, що $a^{n} - a$ a^n - a ділиться на $m$ для кожного цілого $a$ .

Наприклад, коли $n = 2$ n = 2, таких чисел $2$ : $1$ і $2$ . Коли $n = 3$ n = 3, таких чисел $4$ : $1$ , $2$ , $3$ і $6$ . Оскільки таких чисел може бути багато, знайдіть суму всіх цих чисел за модулем $1 0^{9} + 7$ 10^9 + 7.

Гарантовано, що для будь-якого $n > 1$ n > 1 множина таких чисел скінченна.

Вхідні дані

Перший рядок містить натуральне число $T$ ( $1 \leq T \leq 1 0^{5}$ 1 \leq T \leq 10^5) — кількість тестів.

Кожен з наступних $T$ рядків містить ціле число $n$ ( $2 \leq n \leq 2 \times 1 0^{6}$ 2 \leq n \leq 2 \times 10^6).

Вихідні дані

Для кожного $n$ з вхідних даних виведіть відповідь у окремому рядку.

Приклади

Приклад

2
2
3

3
12

Приклад 1

Примітка

Для $n = 2$ n = 2 підходять $m = 1$ m = 1 і $2$ . Їх сума: $1 + 2 = 3$ 1 + 2 = 3.

Для $n = 3$ n = 3 підходять $m = 1$ m = 1, $2$ , $3$ , $6$ . Їх сума: $1 + 2 + 3 + 6 = 12$ 1 + 2 + 3 + 6 = 12.