Ett tal $n$ är givet. Din uppgift är att räkna alla triangulära sekvenser och skriva ut resten vid division av deras antal med $10^9 + 7$. En sekvens kallas triangulär om den uppfyller följande villkor:

• Sekvensens längd överstiger inte $n$.
• Varje element är ett heltal från intervallet $[1, n]$.
• Några tre element i denna sekvens kan vara sidlängderna i en icke-degenererad triangel*.

Exempel på triangulära sekvenser för $n = 100$ är $(1, 1, 1)$ och $(16, 1, 11, 25, 100)$. I den första är sidorna i den icke-degenererade triangeln $(1, 1, 1)$, och i den andra är de $(16, 11, 25)$.

Sekvensen $(16, 1, 11, 84, 100)$ är inte triangulär, eftersom inga tre element bildar sidorna i en icke-degenererad triangel. Sekvensen $(5, 5)$ är inte heller triangulär.

* En triangel är icke-degenererad om den har en positiv area. Ekvivalent ligger dess hörn inte på en rät linje.

Indata

Den enda raden innehåller ett heltal $n$ ($3 \le n \le 200\,000$).

Utdata

Skriv ut ett enda heltal – resten vid division av antalet triangulära sekvenser med $10^9 + 7$ (det vill säga $1000000007$).

Exempel

Indata 1

3

Utdata 1

15

Indata 2

4

Utdata 2

254

Anmärkning

För $n = 3$ finns det $15$ triangulära 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)$.

För $n = 4$ finns det $254$ triangulära 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)$.