Solve the programming task below in a Python markdown code block.
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:

$F_1=F_2=1$
$F_n=F_{n-1}+F_{n-2}$

Given $N$ integers $a_1,a_2,\ldots,a_N$, find $\text{lcm}(F_{a_1},F_{a_2},\ldots,F_{a_N})$, and give your answer modulo $10^9+7$.

Input Format 

The first line of input contains $N$. 

Each of the next $N$ lines contains a number: the $i^{th}$ line contains $a_i$.

Constraints 

$1\leq N\leq100$ 

$1\leq a_i\leq10^9$  

Output Format 

Print a single integer, which is the least common multiple of the ${F}_{a_i}$, modulo $10^9+7$.

Sample Input  

5
1
3
3
6
9

Sample Output  

136

Explanation 

$\text{lcm}(F_1,F_3,F_3,F_6,F_9)=\text{lcm}(1,2,2,8,34)=136$