Số chính phương là số tự nhiên có căn bậc 2 là một số tự nhiên, hay nói cách khác, số chính phương có thể biểu diễn dưới dạng bình phương (lũy thừa bậc 2) của một số tự nhiên. Ví dụ: 4 là số chính phương, vì \(4=2^2\) ; 9 là số chính phương, vì \(9=3^2\).

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 \times 9\); \(144=2 \times 3 \times 4 \times 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, tìm số chính phương lớn nhất bằng tích của một tập các số tự nhiên phân biệt được lấy từ tập các số từ 1 đến \(N\)”. Tuấn suy nghĩ mãi mà chưa trả lời được câu đố mà 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 bằng tích của một tập các số tự nhiên phân biệt được lấy từ tập các số 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 \((10^9 + 7)\).

Input

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

Output

• Ghi ra một dòng duy nhất là kết quả bài toán sau khi đã \(mod\) \(1000000007\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^2\).
• Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^3\).
• Subtask \(3\) (\(40\%\) số điểm): \(N \leq 4 \times 10^4\).

Example

5 

4