Annetaan luku $n$. Tehtäväsi on laskea kaikki kolmiomaiset jonot ja tulostaa niiden lukumäärän jakojäännös, kun se jaetaan luvulla $10^9 + 7$. Jonoa kutsutaan kolmiomaiseksi, jos se täyttää seuraavat ehdot:

• Jonon pituus on enintään $n$.
• Jokainen alkio on kokonaisluku väliltä $[1, n]$.
• Jotkin kolme tämän jonon alkiota voivat olla ei-degeneroituneen kolmion* sivujen pituudet.

Esimerkkejä kolmiomaisista jonoista arvolla $n = 100$ ovat $(1, 1, 1)$ ja $(16, 1, 11, 25, 100)$. Ensimmäisessä ei-degeneroituneen kolmion sivut ovat $(1, 1, 1)$ ja toisessa ne ovat $(16, 11, 25)$.

Jono $(16, 1, 11, 84, 100)$ ei ole kolmiomainen, koska mitkään kolme alkiota eivät muodosta ei-degeneroituneen kolmion sivuja. Jono $(5, 5)$ ei myöskään ole kolmiomainen.

* Kolmio on ei-degeneroitunut, jos sen pinta-ala on positiivinen. Yhtäpitävästi sen kärkipisteet eivät ole samalla suoralla.

Syöte

Ainoa rivi sisältää kokonaisluvun $n$ ($3 \le n \le 200\,000$).

Tuloste

Tulosta yksi kokonaisluku – kolmiomaisten jonojen lukumäärän jakojäännös jaettaessa luvulla $10^9 + 7$ (eli luvulla $1000000007$).

Esimerkit

Syöte 1

3

Tuloste 1

15

Syöte 2

4

Tuloste 2

254

Huomautus

Arvolla $n = 3$ on $15$ kolmiomaista jonoa: $(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)$.

Arvolla $n = 4$ on $254$ kolmiomaista jonoa: $(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)$.