È dato un numero $n$. Il tuo compito è contare tutte le sequenze triangolari e stampare il resto della divisione del loro numero per $10^9 + 7$. Una sequenza è detta triangolare se soddisfa le seguenti condizioni:
- La lunghezza della sequenza non supera $n$.
- Ogni elemento è un intero appartenente all'intervallo $[1, n]$.
- Alcuni tre elementi di questa sequenza possono essere le lunghezze dei lati di un triangolo non degenere*.
Esempi di sequenze triangolari per $n = 100$ sono $(1, 1, 1)$ e $(16, 1, 11, 25, 100)$. Nella prima, i lati del triangolo non degenere sono $(1, 1, 1)$, mentre nella seconda sono $(16, 11, 25)$.
La sequenza $(16, 1, 11, 84, 100)$ non è triangolare, perché nessuna terna di elementi forma i lati di un triangolo non degenere. Anche la sequenza $(5, 5)$ non è triangolare.
* Un triangolo è non degenere se ha un'area positiva. Equivalentemente, i suoi vertici non sono collineari.
Input
L'unica riga contiene un intero $n$ ($3 \le n \le 200\,000$).
Output
Stampa un singolo intero – il resto della divisione del numero di sequenze triangolari per $10^9 + 7$ (cioè $1000000007$).
Esempi
Input 1
3
Output 1
15
Input 2
4
Output 2
254
Note
Per $n = 3$ ci sono $15$ sequenze triangolari: $(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)$.
Per $n = 4$ ci sono $254$ sequenze triangolari: $(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)$.