Перестановки по модулю
Asan
Zaman limiti 1 saniyə-dir
Yaddaş məhdudiyyəti 128 meqabayt
По заданному натуральному числу n вычислите количество перестановок (p[1]
, p[2]
, ..., p[n]
) чисел от 1 до n, таких что для каждого i (1 ≤ i ≤ n), имеет место следующее свойство: p[i]
mod p[i+1]
≤ 2, где p[n+1]
= p[1]
.
Поскольку ответ может быть большим, выведите его по модулю 10^9
+ 7.
Giriş verilənləri
Одно целое число n (1 ≤ n ≤ 10^6
).
Çıxış verilənləri
Выведите одно целое число - количество перестановок, удовлетворяющих условию задачи по модулю 10^9
+ 7.
Пример
Например, для n = 4 Вы посчитаете перестановку [4, 2, 3, 1] так как 4 mod 2 = 0 ≤ 2, 2 mod 3 = 2 ≤ 2, 3 mod 1 = 0 ≤ 2, 1 mod 4 = 1 ≤ 2. Однако перестановка [3, 4, 1, 2] посчитана не будет, так как 3 mod 4 = 3 > 2, что противоречит условию задачи.
Nümunələr
Giriş #1
Çıxış #1
Giriş #2
Çıxış #2
Giriş #3
Çıxış #3
Giriş #4
Çıxış #4
Giriş #5
Çıxış #5
Giriş #6
Çıxış #6
Təqdimatlar 3
Qəbul dərəcəsi 67%