Un nombre $n$ est donné. Votre tâche consiste à compter toutes les séquences triangulaires et à afficher le reste de la division de leur nombre par $10^9 + 7$. Une séquence est dite triangulaire si elle satisfait les conditions suivantes :

• La longueur de la séquence ne dépasse pas $n$.
• Chaque élément est un entier de l'intervalle $[1, n]$.
• Trois éléments de cette séquence peuvent être les longueurs des côtés d'un triangle non dégénéré*.

Des exemples de séquences triangulaires pour $n = 100$ sont $(1, 1, 1)$ et $(16, 1, 11, 25, 100)$. Dans la première, les côtés du triangle non dégénéré sont $(1, 1, 1)$, et dans la seconde, ce sont $(16, 11, 25)$.

La séquence $(16, 1, 11, 84, 100)$ n'est pas triangulaire, car aucun triplet d'éléments ne forme les côtés d'un triangle non dégénéré. La séquence $(5, 5)$ n'est pas non plus triangulaire.

* Un triangle est non dégénéré s'il a une aire strictement positive. De manière équivalente, ses sommets ne sont pas alignés.

Entrée

La seule ligne contient un entier $n$ ($3 \le n \le 200\,000$).

Sortie

Affichez un seul entier – le reste de la division du nombre de séquences triangulaires par $10^9 + 7$ (c'est-à-dire $1000000007$).

Exemples

Entrée 1

3

Sortie 1

15

Entrée 2

4

Sortie 2

254

Note

Pour $n = 3$, il y a $15$ séquences triangulaires : $(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)$.

Pour $n = 4$, il y a $254$ séquences triangulaires : $(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)$.