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 tại Krapina Zagreb. Ông Malnar, một người lớn ủng hộ trật tự, kỷ luật và làm việc chăm chỉ, đã yêu cầu các lập trình viên xếp hàng và đã giao cho mỗi người một số lượng nhiệm vụ nhất định (có thể là không có). Ô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ẽ vui nếu họ nhận được chính xác $i$ nhiệm vụ.

Có bao nhiêu cách khác nhau mà ông Malnar có thể phân phát nhiệm vụ sao cho ít nhất một lập trình viên cảm thấy vui? Hai cách phân phát nhiệm vụ được coi là khác nhau nếu có một lập trình viên và một nhiệm vụ sao cho trong một cách, lập trình viên đó nhận được nhiệm vụ đó trong khi trong cách khác thì họ không nhận.

Input:

• Dòng đầu tiên chứa một số nguyên $N$ $(1 \leq N \leq 350)$.

Output:

• In số cách tìm kiếm được theo modulo $10^9 + 7$.

1

1

314

192940893  

• Subtask 1:($22$%) $1 \leq N \leq 7$
• Subtask 2:($33$%) $1 \leq N \leq 20$
• Subtask 3:($55$%) Không ràng buộc gì thêm