After Derek (of district 5) discovered how to compute the greatest common divisor (gcd) of Fibonacci numbers, he now tried to answer the next obvious question: how does one compute the least common multiple (lcm) of Fibonacci numbers? Unfortunately, Derek found out that this wasn't as easy as the original problem, so he asked you to answer it for him.

The Fibonacci numbers are defined as:

Given integers , find , and give your answer modulo .

Input Format
The first line of input contains .
Each of the next lines contains a number: the line contains .

Constraints

Output Format
Print a single integer, which is the least common multiple of the , modulo .

Sample Input

5
1
3
3
6
9

Sample Output

136

Explanation