Bờm 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: ~ 9 = 1×9 ~; ~ 144 = 2×3×4×6 ~. Bờm 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, Bờm quay sang đố Tuấn, 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? Tuấn 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 Tuấn đư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 ~ 10^9+7 ~.

Dữ liệu vào

• Số nguyên dương ~ n ~ ~ ( n ≤ 4 ×10^4 ) ~

Kết quả

• Một số duy nhất là kết quả bài toán sau khi đã chia lấy dư cho ~ 10^9+7 ~

Ví dụ:

Input 1

5 

Output 1

4