Giải bài trực tuyến

Tối qua yenthanh132 có một giấc mơ lạ:

Trong giấc mơ, yenthanh132 thấy mình tìm thấy được cây đèn thần, vô cùng mừng rỡ, anh ta chà vào cây đèn thần và vị thần đèn xuất hiện. yenthanh132 chưa kịp mở mồm ra để ước thì vị thần đèn đã lên tiếng trước: "Trước đây ta có ra luật là chỉ cho mỗi người 3 điều ước thôi, nhưng vừa nhìn thấy ngươi ta đã thấy chữ "tham"  hiện ra trên trán ngưởi rồi. Vì vậy ta quyết định sẽ tặng cho ngươi thêm 1 điều ước nữa nếu ngươi trả lời được câu đố này của ta, ngươi có đồng ý không?...Bị vị thần nói trúng tim đen nhưng vốn bản tính tham lam nên yenthanh132 đã nhận lời ngay...

Nhưng khổ nỗi vừa nghe vị thần đèn đố xong thì yenthanh132 đã tỉnh giấc. Vừa tiếc nuối vừa ấm ức, "biết vậy lúc nảy đừng có tham, ước luôn có phải tốt hơn không... :( ". Tuy nhiên yenthanh132 vẫn còn nhớ câu đố của vị thần đèn như sau: "Ta đố ngươi biết ta năm nay bao nhiêu tuổi, biết rằng tuổi của ta hiện giờ là một số chính phương, và hơn nữa nó là số chính phương lớn nhất được tạo bởi tích của một tập các số tự nhiên phân biệt từ 1 đến n".

Ngoài bản tính tham lam, yenthanh132 vẫn còn tính tốt là khá mê giải đố nên anh ta vẫn muốn tìm ra lời giải của câu đố này. Nhưng suy nghĩ từ sáng tới giờ này rồi mà vẫn chưa ra. Các bạn hãy giúp yenthanh132 tìm ra lời giải của câu đố này nhé.

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. Số đó có thể rất lớn nên bạn chỉ cầu xuất ra phần dư khi chia số đó cho 1.000.000.007 (10⁹ + 7). Lưu ý là mình cần tìm số lớn nhất, không phải số lớn nhất mod 1.000.000.007

Dữ liệu vào

• Một dòng duy nhất chứa số nguyên dương n.  

Dữ liệu ra

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

Giới hạn:

• n ≤ 10⁷
• Trong 10% số test có n ≤ 20.

Ví dụ

Input 1:
4

Output 1:
4

Input 2:
6

Output 2:
144

Giải thích:
- Test 1: số chính phương lớn nhất là 4 = 1 x 4
- Test 2: số chính phương lớn nhất là 144 = 2 x 3 x 4 x 6