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 ´ 3 ´ 4 ´ 6;  324=2 ´ 3 ´ 6 ´ 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 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 xuất ra phần dư khi chia số đó cho 1000000007.

Dữ liệu: Từ file văn bản CHINHPHUONG.INP có cấu trúc:

Một dòng duy nhất chứa số nguyên dương N. (N ≤ 4.10^4­)  

Kết quả: Ghi vào file văn bản CHINHPHUONG.OUT có cấu trúc:

Một dòng duy nhất là kết quả bài toán sau khi đã mod 1000000007  

Ví dụ

• Subtask 1 (2 điểm): Giả thiết N≤ 10^2­ . 
• Subtask 2 (2 điểm): Giả thiết N≤ 10³ . 
• Subtask 3 (2 điểm): Giả thiết N≤ 4.10⁴ .