Cho số nguyên dương \(n\). Đếm xem có bao nhiêu nhiêu dãy \(A\) thỏa mãn:

• \(A\) không giảm.
• \(A\) có \(n\) phần tử, được đánh chỉ số từ \(1\).
• \(A[n]=n\) và \(A[i] \ge i \ \forall i=\overline{1,n}\).

Vì đáp số có thể lớn, nên kết quả in ra sẽ lấy theo \(mod \ 10^9 + 7\).

Input

• Dòng duy nhất chứa số nguyên dương \(n \ (1 \leq n \leq 10^6)\).

Output

• In ra kết quả đã lấy \(mod \ 10^9 + 7\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 10\).
• Subtask \(2\) (\(70\%\) số điểm): \(n\leq 300\).
• Subtask \(1\) (\(30\%\) số điểm): \(n\leq 3000\).
• Subtask \(2\) (\(70\%\) số điểm): \(n \leq 10^6\).

Example

2 

2