Công ty XXX có ~N~ nhân viên. TGĐ đã yêu cầu các nhân viên xếp thành một hàng và giao cho mỗi người một số nhiệm vụ nhất định (có thể là 0 nhiệm vụ). TGĐ đã giao tổng cộng ~N~ nhiệm vụ khác nhau, biết rằng nhân viên thứ ~i~ sẽ thấy thoả mãn nếu họ được giao đúng ~i~ nhiệm vụ.

Hãy giúp TGĐ xác định xem có bao nhiêm cách giao nhiệm vụ khác nhau, sao cho mỗi cách giao nhiệm vụ có ít nhất một nhân viên thấy thoả mãn.

Hai cách giao nhiệm vụ A và B được tính là khác nhau nếu tồn tại một nhiệm vụ được giao cho một nhân viên trong cách A, nhưng nhiệm vụ đó lại không đươc giao cho nhân viên đó trong cách B.

Input

• Gồm một số nguyên ~N~ ~(1 ≤ N ≤ 350)~ là số nhân viên cũng như là số nhiệm vụ khác nhau được giao.

Output

• Ghi ra số cách giao khác nhau thoả mãn điều kiện dưới dạng module cho ~10^9 + 7~.

Sample Input 1

1

Sample Output 1

1

Sample Output 2

2

Sample Output 2

3

Sample Output 3

314

Sample Output 3

192940893

Subtask

• 17.5% các test có ~1 ≤ N ≤ 7~
• 27.5% các test có ~8 ≤ N ≤ 20~
• 55.0% các test Không có ràng buộc gì thêm.

Giải thích

Ở ví dụ thứ 2 có 3 cách để giao nhiệm vụ để có ít nhất một nhân viên thấy thoả mãn là:

• Cách 1: Nhiệm vụ 1 giao cho nhân viên thứ nhất, nhiệm vụ 2 giao cho nhân viên thứ hai.
• Cách 2: Nhiệm vụ 2 giao cho nhân viên thứ nhất, nhiệm vụ 1 giao cho nhân viên thứ hai.
• Cách 3: Giao cả nhiệm vụ 1 và 2 cho nhân viên thứ hai.