Một hoán vị gồm \(1, 2, \ldots n\) được gọi là đẹp nếu không có các phần tử liền kề có chênh lệch là \(1\).

Cho \(n\), nhiệm vụ của bạn là đếm số lượng hoán vị đẹp.

Input

• Dòng đầu vào duy nhất chứa một số nguyên \(n\).

Output

• In số lượng hoán vị đẹp gồm \(1, 2, \ldots, n\) chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

• \(1 \leq n \leq 1000\)

Example

Sample input

5

Sample output

14