Hoán vị đặc biệt của dãy số ~1, 2, 3, \dots, n~ là dãy số ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le n~; ~a_i \ne a_j~ nếu ~i \ne j~; ~i, j = 1, 2, \dots, n~) thỏa mãn điều kiện: ~1 \times a_1 \le 2 \times a_2 \le \dots \le n \times a_n~.

Yêu cầu: cho số nguyên dương ~n~ (~1 \le n \le 10^{18}~), hãy đếm số lượng hoán vị đặc biệt của dãy số ~1, 2, \dots, n~. Do số lượng hoán vị đặc biệt rất lớn nên chỉ cần đưa ra số dư khi chia kết quả cho ~10^9 + 7~.

Dữ liệu

Một dòng chứa số nguyên dương ~n~.

Kết quả

Một dòng chứa kết quả tìm được.

Ví dụ

HOANVI.INP

5

HOANVI.OUT

8

Giải thích: Có 8 hoán vị đặc biệt là: {1, 2, 3, 4, 5}; {1, 2, 3, 5, 4}; {1, 2, 4, 3, 5}; {1, 3, 2, 4, 5}; {1, 3, 2, 5, 4}; {2, 1, 3, 4, 5}; {2, 1, 3, 5, 4}; {2, 1, 4, 3, 5}.

Giới hạn

• Subtask 1 (10% số test): ~1 \le n \le 20~.
• Subtask 2 (10% số test): ~20 < n \le 10^6~.
• Subtask 3 (80% số test): ~10^6 < n \le 10^{18}~.