Một hoán vị của các số ~1,2,\ldots,n~ được gọi là đẹp nếu không có hai phần tử liền kề nào có hiệu bằng ~1~.

Cho ~n~, nhiệm vụ của bạn là đếm số hoán vị đẹp.

Dữ liệu vào

Dòng duy nhất chứa một số nguyên ~n~.

Kết quả

In ra số hoán vị đẹp của ~1,2,\ldots,n~ modulo ~10^9+7~.

Giới hạn

• ~1 \le n \le 1000~

Ví dụ

Input:

5

Output:

14