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

Yêu cầu: cho số nguyên dương ~n (1≤n≤10^{18}~ ), hãy đếm số lượng hoán vị đặc biệt của dãy số ~1,2,…,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ả: đưa ra một dòng chứa kết quả tìm được.

Ví dụ

INPUT

5

INPUT

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 có ~1≤n≤20;~
• Subtask 2: 10% số test có ~20<n≤10^6;~</li>
• Subtask 3: 80% số test có ~10^6<n≤10^{18}~.</li>