Có ~N~ lập trình viên đang chuẩn bị tham gia vòng 2 của cuộc thi lập trình tại trại đông Krapina Zagreb. Mr.Malnar sẽ là người ra đề cho cuộc thi. Ông ấy đã 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ố nhiệm vụ nhất định (có thể là 0 nhiệm vụ). Mr.Malnar đã giao tổng cộng ~N~ nhiệm vụ khác nhau, biết rằng lập trinh viên thứ ~i~ sẽ thấy thoả mãn nếu họ được giao đúng ~i~ nhiệm vụ.

Hãy giúp Mr.Malnar 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 lập trình 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 lập trình viên trong cách A, nhưng nhiệm vụ đó lại không đươc giao cho lập trình viên đó trong cách B.

Input

• Gồm một số nguyên ~N~ ~(1 \leq N \leq 350)~ là số lập trình 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 1

Input

1

Output

1

Sample 2

Input

2

Output

3

Sample 3

Input

314

Output

192940893

Subtask

• ~5~ test có ~1 \leq N \leq 7~
• ~11~ test tiếp theo có ~1 \leq N \leq 20~
• ~21~ test còn lại không có điều kiện 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 lập trình viên thấy thoả mãn là:

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