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