Cô An có ~N~ chiếc bánh với ~N~ hương vị khác nhau, có ~N~ học sinh, bạn thứ ~i~ sẽ cảm thấy vui nếu được ăn ~i~ cái bánh.

Yêu cầu: Em hãy đếm có bao nhiêu cách để cô An chia bánh mà có ít nhất 1 bạn cảm thấy vui vẻ.

Input

Gồm 1 dòng duy nhất chứa số nguyên ~N~ (~1 \le N \le 350~).

Output

Ghi ra file văn bản CAKE.OUT là số dư của kết quả khi chia cho ~10^9+7~.

Scoring

- Có ~20\%~ số điểm của bài tương ứng với dữ liệu ~N \le 40~.

- Có ~80\%~ số điểm của bài tương ứng với dữ liệu ~N \le 350~.

Sample Input 1

8

Sample Output 1

9184091