Задано число $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)$.