Chia bánh

Cô An có $N$ chiếc bánh với $N$ hương vị khác nhau (hai chiếc bánh bất kỳ là khác nhau) và có $N$ học sinh, đánh số từ $1$ đến $N$. Bạn thứ $i$ sẽ cảm thấy vui nếu được ăn đúng $i$ chiếc bánh.

Cô An chia hết $N$ chiếc bánh cho các học sinh: mỗi chiếc bánh được đưa cho đúng một học sinh, một học sinh có thể nhận nhiều chiếc hoặc không nhận chiếc nào. Hai cách chia được coi là khác nhau nếu có một chiếc bánh được đưa cho hai học sinh khác nhau trong hai cách chia đó.

Yêu cầu: Hãy đếm số cách để cô An chia bánh sao cho có ít nhất $1$ học sinh cảm thấy vui vẻ.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên $N$ ($1\le N\le 350$).

Dữ liệu ra

In ra số cách chia bánh thỏa mãn yêu cầu, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le N\le 350$.

Subtasks

• Subtask 1 ($20\%$ số điểm): $N\le 40$.
• Subtask 2 ($80\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ