Trong số học, sự phân hoạch một số nguyên dương \(n\) là cách viết số đó dưới dạng tổng của các số nguyên dương, không phân biệt thứ tự. Số lượng các cách phân hoạch số \(n\) được tính bởi hàm phân hoạch, ký hiệu là \(p(n)\). Ví dụ, ta có \(p(4) = 5\) vì có các cách phân tích:

• \(4=1+1+1+1\)
• \(4=1+1+2\)
• \(4=1+3\)
• \(4=2+2\)
• \(4=4\)

Cho trước số nguyên dương \(n\), viết chương trình tính giá trị của \(p(n)\). Vì giá trị \(p(n)\) có thể rất lớn nên kết quả in ra theo modulo \(10^9 + 7\).

Input Specification

Gồm số nguyên dương \(n\) được ghi trên một dòng duy nhất.

Output Specification

In kết quả trên một dòng duy nhất.

Constraints

\(n \leq 10^4\)

Input Sample

4

Output Sample

5