Tích chính phương lớn nhất

Bạn An rất thích các số chính phương, muốn tìm hiểu về nó, và biết rằng số chính phương cũng được biểu diễn bằng tích của một tập các số tự nhiên phân biệt. Chẳng hạn: $144=2\times 3\times 4\times 6$; $324=2\times 3\times 6\times 9$. Bạn An hay ngẫm nghĩ về nó mọi lúc khi có thời gian rảnh. Hôm nay, giờ giải lao trên lớp, An quay sang hỏi Hưng: với số tự nhiên $N$ cho trước thì số chính phương lớn nhất được biểu diễn bằng tích của một tập các số tự nhiên phân biệt từ $1$ đến $N$ là bao nhiêu? Hưng suy nghĩ mãi mà chưa trả lời được câu đố và thời gian thì ít quá.

Yêu cầu: Cho một số nguyên dương $N$, hãy giúp Hưng đưa ra số chính phương lớn nhất là tích của một tập các số tự nhiên phân biệt từ $1$ đến $N$. Số đó có thể rất lớn nên chỉ cần in ra phần dư khi chia số đó cho $1000000007$.

Dữ liệu vào

Một dòng duy nhất chứa số nguyên dương $N$.

Dữ liệu ra

In ra một số nguyên duy nhất là kết quả bài toán sau khi đã lấy phần dư khi chia cho $1000000007$.

Ràng buộc

• $1\le N\le 4\times {10}^4$.

Subtasks

• Subtask 1 ($33\%$ số điểm): $N\le {10}^2$.
• Subtask 2 ($33\%$ số điểm): ${10}^2<N\le {10}^3$.
• Subtask 3 ($34\%$ số điểm): ${10}^3<N\le 4\times {10}^4$.

Ví dụ