Simple question

Time Limit: 4000 ms Memory Limit: 125536 KiB

Problem Description

Winter is too boring.
Lin wants to lie on the bed in the dormitory to watch the mobile phone, and is not willing to go out to study. But his teammates disliked his level and thought he should try to learn the algorithm. Lin took an algorithm book from his bed and started to look at it. After seeing a question, he thought it was too simple, just as proof of his study. But he is lazy to write, so he gave you this question. Now give you an integer n, you need to find a minimum positive integer m, so that m can be divisible by in all 1~n numbers. Since m may be large, it is output after modulo 100000007.

Input

There are no more than 20 test cases.

For each test case:

The line contains one integer n. ( 1 <= n <= 100000000 ) 

Output

For each test case, print one integer m.

Sample Input

1
5

Sample Output

1
60

Hint

Source

Mercury_Lc