Chief, your situation is miserable in Calculus. You know that if some miracle doesn't happen, you are going to spend the next summer here. Obviously, you don't want to do that. So, you hatch a plan to hack into your instructor's computer system and obtain the exam paper. Given that you are good at hacking, you manage to obtain the exam paper but unfortunately, the text is encrypted. All is not lost yet!  You see some numbers written on the paper. Quickly, you figure out that the key to decrypt the text is the lowest common multiple of the given numbers(mod 10007).

Input

The input consists of multiple lines. Each line consists of a number n(1 <= n  <= 10^4). End of input is marked by 0.

Output

Output a single number which is the L.C.M. of the input numbers modulo 10007.

Example

Input: 
2
3
4
0

Output: 
12

Please note that zero is just an indicator for the end of input. It is guaranted that the input will have atleast two lines.