Với số nguyên dương \(n\), một hoán vị của \(\{1, 2, \dots, n\}\) được gọi là hoán vị đẹp nếu viết liên tiếp hoán vị đó tạo thành một số nguyên chia hết cho \(11\).

Yêu cầu: Cho \(n\), đếm số hoán vị đẹp.

Input

• Gồm một dòng duy nhất chứa số nguyên dương \(n\).

Output

• Gồm một dòng chứa một số là số hoán vị đẹp chia dư cho \(10^9 + 7\).

Example

3

2

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(40\%\) số điểm): \(n \le 100\).

Nguồn: Thầy Đông '21