Có tổng cộng ~N~ lập trình viên trẻ đang chuẩn bị cho phần hai của mùa thi lập trình trong một trại đông tại Krapina Zagreb. Ông Malnar, một người rất đề cao trật tự, kỷ luật và chăm chỉ, đã yêu cầu các lập trình viên xếp thành một hàng và giao cho mỗi người một số lượng bài toán nhất định (có thể là ~0~).

Tổng cộng có ~N~ bài toán khác nhau được giao, và ông biết rằng lập trình viên thứ ~i~ trong hàng sẽ cảm thấy hài lòng nếu họ nhận đúng ~i~ bài toán.

Hỏi có bao nhiêu cách khác nhau để ông Malnar phân phát các bài toán sao cho có ít nhất một lập trình viên cảm thấy hài lòng?

Hai cách phân phát được coi là khác nhau nếu tồn tại một lập trình viên và một bài toán sao cho trong một cách, lập trình viên đó nhận bài toán đó, còn trong cách kia thì không.

Input

• Dòng đầu tiên chứa một số nguyên ~N~ ~(1 ≤ N ≤ 350)~ như mô tả trong đề bài.

Output

• In ra số cách thỏa mãn, lấy modulo ~10^9 + 7~.

Scoring

• Subtask ~1\ (20\%):~ ~1 \le N \le 7~
• Subtask ~2\ (30\%):~ ~1 \le N \le 20~
• Subtask ~3\ (50\%):~ Không có ràng buộc gì thêm

Sample Input 1

1

Sample Output 1

1

Sample Input 2

2

Sample Output 2

3

Sample Input 3

314

Sample Output 3

192940893

Notes

Giải thích ví dụ thứ hai: Các cách phân phát sao cho có ít nhất một lập trình viên hài lòng là:

1. Bài 1 cho lập trình viên 1, bài 2 cho lập trình viên 2.
2. Bài 2 cho lập trình viên 1, bài 1 cho lập trình viên 2.
3. Cả hai bài đều cho lập trình viên 2.