Перестановки по модулю

По заданному натуральному числу 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.

Входные данные

Одно целое число n (1 ≤ n ≤ 10^6).

Выходные данные

Выведите одно целое число - количество перестановок, удовлетворяющих условию задачи по модулю 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, что противоречит условию задачи.

Примеры