Перестановки за модулем#10888
По заданому натуральному числу обчисліть кількість перестановок (p_1, p_2, \ldots, p_n) чисел від до , таких що для кожного (1 \le i \le n) виконується наступна умова: p_i \mod p_{i+1} \le 2, де p_{n+1} = p_1.
Оскільки відповідь може бути великою, виведіть її за модулем 10^9 + 7.
Одне ціле число (1 \le n \le 10^6).
Виведіть одне ціле число - кількість перестановок, що задовольняють умові задачі за модулем 10^9 + 7.
Наприклад, для n = 4 перестановка [, , , ] буде врахована, оскільки 4 \mod 2 = 0 \le 2, 2 \mod 3 = 2 \le 2, 3 \mod 1 = 0 \le 2, 1 \mod 4 = 1 \le 2. Проте перестановка [, , , ] не буде врахована, оскільки 3 \mod 4 = 3 > 2, що суперечить умові задачі.
Приклад 1
Приклад 2
Приклад 3
Приклад 4
Приклад 5
Приклад 6