Con gái rất khó hiểu, càng khó hiểu hơn khi họ là crush của bạn, do vậy, theo nghiên cứu của chúng tôi, bạn cần phải làm quen với rất nhiều thứ khó hiểu để hiểu hơn crush của bạn, do đó, chúng tôi đưa ra bài toán sau (mà theo tính toán độ khó hiểu của nó xấp xỉ bằng $\frac{1}{10^{18}}$ độ khó hiểu của con gái) để bạn có thể dần làm quen với sự khó hiểu, bài toán như sau:

Cho $1$ số nguyên dương $n$, hãy tính $F(n)$ với $F(n)$ là $\Sigma \frac{(i\ +\ j\ +\ k)!}{i!\times j!\times k!}$ sao cho $i,j,k\in N$ và $i+j+2k=n$.

Bạn hãy giải bài toán để có thể hiểu hơn về sự khó hiểu nhé.

Input

• Gồm $1$ dòng duy nhất là số nguyên dương $n$ ($1\le n\le 2.10^6$).

Output

• Gồm $1$ số nguyên là câu trả lời cho $F(n)$ . Kết quả có thể rất lớn nên hãy chia lấy dư cho $10^9 + 7$.

Subtasks

• Subtask 1: Đảm bảo $n\le 10$. (15 điểm)
• Subtask 2: Đảm bảo $n\le 3.10^3$. (45 điểm)
• Subtask 3: Không có ràng buộc gì thêm. (150 điểm)

Example

7

268