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 ~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:

• Số nguyên dương ~N~ ~(N \le 4.10^4).~

Kết quả:

• Kết quả bài toán sau khi đã ~\mod 1000000007~.

Ví dụ

Dữ liệu vào

7

Dữ liệu ra

144