Et tall $n$ er gitt. Din oppgave er å telle alle triangulære sekvenser og skrive ut resten ved å dele antallet deres på $10^9 + 7$. En sekvens kalles triangulær hvis den oppfyller følgende betingelser:

• Lengden på sekvensen overstiger ikke $n$.
• Hvert element er et heltall fra intervallet $[1, n]$.
• Noen tre elementer i denne sekvensen kan være sidelengdene i en ikke-degenerert trekant*.

Eksempler på triangulære sekvenser for $n = 100$ er $(1, 1, 1)$ og $(16, 1, 11, 25, 100)$. I den første er sidene i den ikke-degenererte trekanten $(1, 1, 1)$, og i den andre er de $(16, 11, 25)$.

Sekvensen $(16, 1, 11, 84, 100)$ er ikke triangulær, fordi ingen tre elementer danner sidene i en ikke-degenerert trekant. Sekvensen $(5, 5)$ er heller ikke triangulær.

* En trekant er ikke-degenerert hvis den har et positivt areal. Ekvivalent ligger ikke hjørnene på en rett linje.

Inndata

Den eneste linjen inneholder et heltall $n$ ($3 \le n \le 200\,000$).

Utdata

Skriv ut ett enkelt heltall – resten ved å dele antallet triangulære sekvenser på $10^9 + 7$ (det vil si $1000000007$).

Eksempler

Inndata 1

3

Utdata 1

15

Inndata 2

4

Utdata 2

254

Merk

For $n = 3$ er det $15$ triangulære sekvenser: $(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)$.

For $n = 4$ er det $254$ triangulære sekvenser: $(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)$.