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 tìm 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~. Vì kết quả có thể rất lớn nên chỉ cần xuất ra phần dư khi chia số đó cho ~1000000007~.

Input

• Một dòng duy nhất chứa số nguyên dương ~N~ (~N \le 4 \times 10^4~).

Output

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

Sample Input 1

7

Sample Output 1

144