Fermanın kiçik teoremi#3723

Fermanın kiçik teoremi

4 saniyə

256 meqabayt

Çətin

Fermatın Kiçik Teoremi bizə bildirir ki, istənilən sadə $p$ ədədi və istənilən tam $a$ üçün $a^{p} - a$ a^p - a ifadəsi $p$ -yə bölünür. Bu məsələdə biz oxşar bir anlayışı araşdırırıq.

Verilmiş $n > 1$ n > 1 təbii ədədi üçün, sizin tapşırığınız belə $m$ təbii ədədləri müəyyən etməkdir ki, istənilən tam $a$ üçün $a^{n} - a$ a^n - a ifadəsi $m$ -ə bölünsün.

Məsələn, $n = 2$ n = 2 üçün belə $2$ ədəd var: $1$ və $2$ . $n = 3$ n = 3 üçün isə belə $4$ ədəd var: $1$ , $2$ , $3$ və $6$ . Belə ədədlərin sayı çox ola biləcəyi üçün, onların cəmini $1 0^{9} + 7$ 10^9 + 7 moduluna görə hesablayın.

Zəmanət verilir ki, istənilən $n > 1$ n > 1 üçün belə ədədlərin sayı sonludur.

Giriş

Birinci sətrdə təbii ədəd $T$ ( $1 \leq T \leq 1 0^{5}$ 1 \leq T \leq 10^5) — testlərin sayı verilir.

Növbəti $T$ sətrin hər birində $n$ ( $2 \leq n \leq 2 \times 1 0^{6}$ 2 \leq n \leq 2 \times 10^6) tam ədədi verilir.

Çıxış

Girişdə verilmiş hər $n$ üçün cavabı ayrıca sətrdə çap edin.

Nümunələr

Nümunə

2
2
3

3
12

Nümunə 1

Qeyd

$n = 2$ n = 2 üçün uyğun $m$ ədədləri $1$ və $2$ -dir. Cəmi $1 + 2 = 3$ 1 + 2 = 3.

$n = 3$ n = 3 üçün uyğun $m$ ədədləri $1$ , $2$ , $3$ və $6$ -dır. Cəmi $1 + 2 + 3 + 6 = 12$ 1 + 2 + 3 + 6 = 12.