Dana jest liczba $n$. Twoim zadaniem jest zliczenie wszystkich ciągów trójkątnych i wypisanie reszty z dzielenia ich liczby przez $10^9 + 7$. Ciąg nazywamy trójkątnym, jeśli spełnia następujące warunki:

• Długość ciągu nie przekracza $n$.
• Każdy element jest liczbą całkowitą z przedziału $[1, n]$.
• Pewne trzy elementy tego ciągu mogą być długościami boków niezdegenerowanego trójkąta*.

Przykładowymi ciągami trójkątnymi dla $n = 100$ są $(1, 1, 1)$ oraz $(16, 1, 11, 25, 100)$. W pierwszym boki niezdegenerowanego trójkąta to $(1, 1, 1)$, a w drugim $(16, 11, 25)$.

Ciąg $(16, 1, 11, 84, 100)$ nie jest trójkątny, ponieważ żadne trzy elementy nie tworzą boków niezdegenerowanego trójkąta. Ciąg $(5, 5)$ również nie jest trójkątny.

* Trójkąt jest niezdegenerowany, jeśli ma dodatnie pole. Równoważnie, jego wierzchołki nie są współliniowe.

Wejście

Jedyny wiersz zawiera liczbę całkowitą $n$ ($3 \le n \le 200\,000$).

Wyjście

Wypisz jedną liczbę całkowitą – resztę z dzielenia liczby ciągów trójkątnych przez $10^9 + 7$ (czyli $1000000007$).

Przykłady

Wejście 1

3

Wyjście 1

15

Wejście 2

4

Wyjście 2

254

Uwaga

Dla $n = 3$ istnieje $15$ ciągów trójkątnych: $(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)$.

Dla $n = 4$ istnieją $254$ ciągi trójkątne: $(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)$.