Se da un número $n$. Tu tarea es contar todas las secuencias triangulares e imprimir el resto de dividir su cantidad entre $10^9 + 7$. Una secuencia se llama triangular si satisface las siguientes condiciones:
- La longitud de la secuencia no excede $n$.
- Cada elemento es un entero del intervalo $[1, n]$.
- Algunos tres elementos de esta secuencia pueden ser las longitudes de los lados de un triángulo no degenerado*.
Ejemplos de secuencias triangulares para $n = 100$ son $(1, 1, 1)$ y $(16, 1, 11, 25, 100)$. En la primera, los lados del triángulo no degenerado son $(1, 1, 1)$, y en la segunda son $(16, 11, 25)$.
La secuencia $(16, 1, 11, 84, 100)$ no es triangular, porque ningún trío de elementos forma los lados de un triángulo no degenerado. La secuencia $(5, 5)$ tampoco es triangular.
* Un triángulo es no degenerado si tiene un área positiva. Equivalentemente, sus vértices no son colineales.
Entrada
La única línea contiene un entero $n$ ($3 \le n \le 200\,000$).
Salida
Imprime un solo entero: el resto de dividir el número de secuencias triangulares entre $10^9 + 7$ (es decir, $1000000007$).
Ejemplos
Entrada 1
3
Salida 1
15
Entrada 2
4
Salida 2
254
Nota
Para $n = 3$ hay $15$ secuencias triangulares: $(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)$.
Para $n = 4$ hay $254$ secuencias triangulares: $(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)$.