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\).

Scoring

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

Example

1 

1

2 

3

314 

192940893