Modul üzrə Permutasiyalar

Verilmiş təbii ədəd n üçün 1-dən n-ə qədər olan ədədlərin (p[1], p[2], ..., p[n]) elə permutasiyalarının sayını hesablayın ki, hər bir i üçün (1 ≤ i ≤ n) aşağıdakı şərt yerinə yetirilsin: p[i] mod p[i+1] ≤ 2, burada p[n+1] = p[1] qəbul edilir.

Cavab böyük ola biləcəyi üçün onu 10^9 + 7 moduluna görə çıxarın.

Giriş

Bir tam ədəd n (1 ≤ n ≤ 10^6).

Çıxış

Tapşırığın şərtini ödəyən permutasiyaların sayını 10^9 + 7 moduluna görə bir tam ədəd kimi çıxarın.

Nümunə

Məsələn, n = 4 üçün [4, 2, 3, 1] permutasiyası şərti ödəyir, çünki 4 mod 2 = 0 ≤ 2, 2 mod 3 = 2 ≤ 2, 3 mod 1 = 0 ≤ 2, 1 mod 4 = 1 ≤ 2. Lakin [3, 4, 1, 2] permutasiyası şərti ödəmir, çünki 3 mod 4 = 3 > 2, bu isə tapşırığın şərtinə ziddir.