Дано число $n$. Ваша задача — посчитать все треугольные последовательности и вывести остаток от деления их количества на $10^9 + 7$. Последовательность называется треугольной, если она удовлетворяет следующим условиям:

• Длина последовательности не превышает $n$.
• Каждый элемент является целым числом из отрезка $[1, n]$.
• Некоторые три элемента этой последовательности могут быть длинами сторон невырожденного треугольника*.

Примерами треугольных последовательностей для $n = 100$ являются $(1, 1, 1)$ и $(16, 1, 11, 25, 100)$. В первой стороны невырожденного треугольника равны $(1, 1, 1)$, а во второй — $(16, 11, 25)$.

Последовательность $(16, 1, 11, 84, 100)$ не является треугольной, так как никакие три элемента не образуют стороны невырожденного треугольника. Последовательность $(5, 5)$ также не является треугольной.

* Треугольник называется невырожденным, если его площадь положительна. Эквивалентно, его вершины не лежат на одной прямой.

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

Единственная строка содержит целое число $n$ ($3 \le n \le 200\,000$).

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

Выведите одно целое число — остаток от деления количества треугольных последовательностей на $10^9 + 7$ (то есть на $1000000007$).

Примеры

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

3

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

15

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

4

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

254

Примечание

Для $n = 3$ существует $15$ треугольных последовательностей: $(1,1,1), (1,2,2), (1,3,3), (2,1,2), (2,2,1), (2,2,2), (2,2,3), (2,3,2), (2,3,3), (3,1,3), (3,2,2), (3,2,3), (3,3,1), (3,3,2), (3,3,3)$.

Для $n = 4$ существует $254$ треугольные последовательности: $(1,1,1), (1,1,1,1), (1,1,1,2), (1,1,1,3), (1,1,1,4), (1,1,2,1), \dots, (4,4,2,4), (4,4,3), (4,4,3,1), (4,4,3,2), (4,4,3,3), (4,4,3,4), (4,4,4), (4,4,4,1), (4,4,4,2), (4,4,4,3), (4,4,4,4)$.