Diberikan sebuah bilangan $n$. Tugas Anda adalah menghitung semua barisan segitiga dan mengeluarkan sisa pembagian jumlahnya dengan $10^9 + 7$. Sebuah barisan disebut barisan segitiga jika memenuhi kondisi berikut:

• Panjang barisan tidak melebihi $n$.
• Setiap elemen adalah bilangan bulat dari interval $[1, n]$.
• Terdapat tiga elemen dari barisan ini yang dapat menjadi panjang sisi-sisi dari sebuah segitiga tak-degenerat*.

Contoh barisan segitiga untuk $n = 100$ adalah $(1, 1, 1)$ dan $(16, 1, 11, 25, 100)$. Pada barisan pertama, sisi-sisi segitiga tak-degeneratnya adalah $(1, 1, 1)$, dan pada barisan kedua adalah $(16, 11, 25)$.

Barisan $(16, 1, 11, 84, 100)$ bukan barisan segitiga, karena tidak ada tiga elemen yang membentuk sisi-sisi segitiga tak-degenerat. Barisan $(5, 5)$ juga bukan barisan segitiga.

* Sebuah segitiga dikatakan tak-degenerat jika memiliki luas positif. Secara ekuivalen, titik-titik sudutnya tidak segaris (kolinear).

Masukan

Satu-satunya baris berisi sebuah bilangan bulat $n$ ($3 \le n \le 200\,000$).

Keluaran

Cetak satu bilangan bulat – sisa pembagian jumlah barisan segitiga dengan $10^9 + 7$ (yaitu $1000000007$).

Contoh

Masukan 1

3

Keluaran 1

15

Masukan 2

4

Keluaran 2

254

Catatan

Untuk $n = 3$ terdapat $15$ barisan segitiga: $(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)$.

Untuk $n = 4$ terdapat $254$ barisan segitiga: $(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)$.