Sau nhiều bước tuyển lựa gắt gao, tỉnh QN đã chọn được \(N\) học sinh để tiếp tục bồi dưỡng cho vòng thi chọn HSG Quốc gia sắp tới. Thầy Hùng cho \(N\) học sinh này xếp thành một hàng và thầy giao cho mỗi học sinh một số lượng bài tập nhất định (có thể bằng \(0\)) để các bạn luyện tập. Thầy Hùng giao tổng cộng \(N\) bài tập khác nhau và thầy biết rằng học sinh thứ \(i\) sẽ hài lòng nếu được giao đúng \(i\) bài tập.

Hãy giúp thầy Hùng tính số cách giao bài tập để ít nhất một trong \(N\) học sinh hài lòng. Hai cách giao được xem là khác nhau nếu tồn tại một học sinh được giao một bài tập ở cách giao này nhưng lại không được giao bài tập đó ở cách giao còn lại.

Input

Gồm một số nguyên dương \(N\) được nhắc đến trong đề bài.

Output

Số cách tìm được sau khi chia lấy số dư cho \(10^9+7\).

Ví dụ

Sample input 1

1

Sample output 1

1

Sample input 2

2

Sample output 2

3

Sample input 3

314

Sample output 3

192940893

Giải thích test ví dụ thứ nhì

Ba cách giao bài tập để tồn tại ít nhất một học sinh thỏa mãn là:

• Giao bài tập thứ nhất cho học sinh thứ nhất, bài tập thứ nhì cho học sinh thứ nhì.
• Giao bài tập thứ nhì cho học sinh thứ nhất, bài tập thứ nhất cho học sinh thứ nhì.
• Giao cả hai bài tập cho học sinh thứ nhì.

Ràng buộc

• Subtask 1: (13 điểm) \(N\leq 7\).
• Subtask 2: (30 điểm) \(N\leq 20\).
• Subtask 3: (57 điểm) \(N\leq 350\).