Có tổng cộng ~N~ lập trình viên trẻ đang chuẩn bị cho phần thứ hai của mùa thi đấu trong một trại mùa đông ở Krapina Zagreb. Ông Malnar, người rất ủng hộ trật tự, kỷ luật và làm việc chăm chỉ, đã bảo các lập trình viên xếp hàng và phân phát cho mỗi người một số nhiệm vụ nhất định (có thể là không). Ông đã phát tổng cộng ~N~ nhiệm vụ khác nhau và ông biết rằng lập trình viên thứ ~i~ trong hàng sẽ cảm thấy hạnh phúc nếu họ nhận được chính xác ~i~ nhiệm vụ.

Hỏi có bao nhiêu cách khác nhau mà ông Malnar có thể phân phát các nhiệm vụ sao cho ít nhất một lập trình viên cảm thấy hạnh phúc? Hai cách phân phát nhiệm vụ được coi là khác nhau nếu tồn tại một lập trình viên và một nhiệm vụ sao cho theo một cách thì lập trình viên đó nhận được nhiệm vụ đó còn theo cách kia thì không.

input

Dòng đầu tiên chứa một số nguyên ~N~ ~(1 \leq N \leq 350)~ từ mô tả bài toán.

Output

Xuất ra số cách tìm được theo modulo ~10^9 + 7~.

Chú ý

• Điểm cho bài toán phụ 1: 22 điểm với ~1 \leq N \leq 7~
• Điểm cho bài toán phụ 2: 33 điểm với ~1 \leq N \leq 20~.
• Điểm cho bài toán phụ 3: 55 điểm không có ràng buộc bổ sung.

Sample Input 1

1

Sample Ouput 1

1

Sample Input 2

2

Sample Ouput 2

3

Sample Input 3

314

Sample Ouput 3

192940893

Giải thích

Giải thích cho ví dụ thứ hai: Các cách phân phối nhiệm vụ mà ít nhất một lập trình viên cảm thấy hạnh phúc bao gồm:

• Nhiệm vụ đầu tiên cho lập trình viên đầu tiên, nhiệm vụ thứ hai cho lập trình viên thứ hai.
• Nhiệm vụ thứ hai cho lập trình viên đầu tiên, nhiệm vụ đầu tiên cho lập trình viên thứ hai.
• Cả hai nhiệm vụ cho lập trình viên thứ hai.