Задачі
Перестановки по модулю
Перестановки по модулю
По заданному натуральному числу n вычислите количество перестановок (p1
, p2
, ..., pn
) чисел от 1 до n, таких что для каждого i (1 ≤ i ≤ n), имеет место следующее свойство: pi
mod pi+1
≤ 2, где pn+1
= p1
.
Поскольку ответ может быть большим, выведите его по модулю 109
+ 7.
Входные данные
Одно целое число n (1 ≤ n ≤ 106
).
Выходные данные
Выведите одно целое число - количество перестановок, удовлетворяющих условию задачи по модулю 109
+ 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, что противоречит условию задачи.
Вхідні дані #1
1
Вихідні дані #1
1
Вхідні дані #2
2
Вихідні дані #2
2
Вхідні дані #3
3
Вихідні дані #3
6
Вхідні дані #4
4
Вихідні дані #4
16
Вхідні дані #5
5
Вихідні дані #5
40
Вхідні дані #6
1000000
Вихідні дані #6
581177467