Eine Zahl $n$ ist gegeben. Deine Aufgabe ist es, alle Dreiecksfolgen zu zählen und den Rest bei der Division ihrer Anzahl durch $10^9 + 7$ auszugeben. Eine Folge heißt Dreiecksfolge, wenn sie die folgenden Bedingungen erfüllt:

• Die Länge der Folge überschreitet $n$ nicht.
• Jedes Element ist eine ganze Zahl aus dem Intervall $[1, n]$.
• Irgendwelche drei Elemente dieser Folge können die Seitenlängen eines nicht-entarteten Dreiecks* sein.

Beispiele für Dreiecksfolgen für $n = 100$ sind $(1, 1, 1)$ und $(16, 1, 11, 25, 100)$. Im ersten Fall sind die Seiten des nicht-entarteten Dreiecks $(1, 1, 1)$, und im zweiten sind sie $(16, 11, 25)$.

Die Folge $(16, 1, 11, 84, 100)$ ist keine Dreiecksfolge, da keine drei Elemente die Seiten eines nicht-entarteten Dreiecks bilden. Die Folge $(5, 5)$ ist ebenfalls keine Dreiecksfolge.

* Ein Dreieck ist nicht-entartet, wenn es einen positiven Flächeninhalt hat. Äquivalent dazu liegen seine Eckpunkte nicht auf einer Geraden.

Eingabe

Die einzige Zeile enthält eine ganze Zahl $n$ ($3 \le n \le 200\,000$).

Ausgabe

Gib eine einzige ganze Zahl aus – den Rest bei der Division der Anzahl der Dreiecksfolgen durch $10^9 + 7$ (also $1000000007$).

Beispiele

Eingabe 1

3

Ausgabe 1

15

Eingabe 2

4

Ausgabe 2

254

Hinweis

Für $n = 3$ gibt es $15$ Dreiecksfolgen: $(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)$.

Für $n = 4$ gibt es $254$ Dreiecksfolgen: $(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)$.