Gefin er tala $n$. Verkefni þitt er að telja allar þríhyrningsrunur og prenta afganginn þegar fjöldi þeirra er deildur með $10^9 + 7$. Runa kallast þríhyrningsruna ef hún uppfyllir eftirfarandi skilyrði:

• Lengd rununnar fer ekki yfir $n$.
• Hvert stak er heiltala á bilinu $[1, n]$.
• Einhver þrjú stök þessarar runu geta verið hliðarlengdir óúrkynjaðs þríhyrnings*.

Dæmi um þríhyrningsrunur fyrir $n = 100$ eru $(1, 1, 1)$ og $(16, 1, 11, 25, 100)$. Í þeirri fyrri eru hliðar óúrkynjaða þríhyrningsins $(1, 1, 1)$ og í þeirri síðari eru þær $(16, 11, 25)$.

Runan $(16, 1, 11, 84, 100)$ er ekki þríhyrningsruna, vegna þess að engin þrjú stök mynda hliðar óúrkynjaðs þríhyrnings. Runan $(5, 5)$ er heldur ekki þríhyrningsruna.

* Þríhyrningur er óúrkynjaður ef hann hefur jákvætt flatarmál. Jafngilt því er að hornpunktar hans liggi ekki á sömu línu.

Inntak

Eina línan inniheldur heiltölu $n$ ($3 \le n \le 200\,000$).

Úttak

Prentaðu eina heiltölu – afganginn þegar fjöldi þríhyrningsruna er deildur með $10^9 + 7$ (þ.e. $1000000007$).

Dæmi

Inntak 1

3

Úttak 1

15

Inntak 2

4

Úttak 2

254

Athugasemd

Fyrir $n = 3$ eru $15$ þríhyrningsrunur: $(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)$.

Fyrir $n = 4$ eru $254$ þríhyrningsrunur: $(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)$.