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)$.