Cho một số $n$. Nhiệm vụ của bạn là đếm tất cả các dãy tam giác và in ra số dư khi chia số lượng của chúng cho $10^9 + 7$. Một dãy được gọi là dãy tam giác nếu nó thỏa mãn các điều kiện sau:

• Độ dài của dãy không vượt quá $n$.
• Mỗi phần tử là một số nguyên thuộc đoạn $[1, n]$.
• Có ba phần tử nào đó của dãy này có thể làm độ dài ba cạnh của một tam giác không suy biến*.

Ví dụ các dãy tam giác với $n = 100$ là $(1, 1, 1)$ và $(16, 1, 11, 25, 100)$. Ở dãy thứ nhất, ba cạnh của tam giác không suy biến là $(1, 1, 1)$, và ở dãy thứ hai, chúng là $(16, 11, 25)$.

Dãy $(16, 1, 11, 84, 100)$ không phải là dãy tam giác, vì không có ba phần tử nào tạo thành ba cạnh của một tam giác không suy biến. Dãy $(5, 5)$ cũng không phải là dãy tam giác.

* Một tam giác là không suy biến nếu nó có diện tích dương. Một cách tương đương, các đỉnh của nó không thẳng hàng.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên $n$ ($3 \le n \le 200\,000$).

Kết quả

In ra một số nguyên duy nhất – số dư khi chia số lượng dãy tam giác cho $10^9 + 7$ (tức là $1000000007$).

Ví dụ

Dữ liệu vào 1

3

Kết quả 1

15

Dữ liệu vào 2

4

Kết quả 2

254

Ghi chú

Với $n = 3$ có $15$ dãy tam giác: $(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)$.

Với $n = 4$ có $254$ dãy tam giác: $(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)$.