You are given a tuple generator 𝑓(𝑘)=(𝑓(𝑘)1,𝑓(𝑘)2,…,𝑓(𝑘)𝑛)f(k)=(f1(k),f2(k),…,fn(k)), where 𝑓(𝑘)𝑖=(𝑎𝑖⋅𝑓(𝑘−1)𝑖+𝑏𝑖)mod𝑝𝑖fi(k)=(ai⋅fi(k−1)+bi)modpi and 𝑓(0)=(𝑥1,𝑥2,…,𝑥𝑛)f(0)=(x1,x2,…,xn). Here 𝑥mod𝑦xmody denotes the remainder of 𝑥x when divided by 𝑦y. All 𝑝𝑖pi are primes.

One can see that with fixed sequences 𝑥𝑖xi, 𝑦𝑖yi, 𝑎𝑖ai the tuples 𝑓(𝑘)f(k) starting from some index will repeat tuples with smaller indices. Calculate the maximum number of different tuples (from all 𝑓(𝑘)f(k) for 𝑘≥0k≥0) that can be produced by this generator, if 𝑥𝑖xi, 𝑎𝑖ai, 𝑏𝑖bi are integers in the range [0,𝑝𝑖−1][0,pi−1] and can be chosen arbitrary. The answer can be large, so print the remainder it gives when divided by 109+7109+7

Input

The first line contains one integer 𝑛n (1≤𝑛≤2⋅1051≤n≤2⋅105) — the number of elements in the tuple.

The second line contains 𝑛n space separated prime numbers — the modules 𝑝1,𝑝2,…,𝑝𝑛p1,p2,…,pn (2≤𝑝𝑖≤2⋅1062≤pi≤2⋅106).

Output

Print one integer — the maximum number of different tuples modulo 109+7109+7.

Note

In the first example we can choose next parameters: 𝑎=[1,1,1,1]a=[1,1,1,1], 𝑏=[1,1,1,1]b=[1,1,1,1], 𝑥=[0,0,0,0]x=[0,0,0,0], then 𝑓(𝑘)𝑖=𝑘mod𝑝𝑖fi(k)=kmodpi.

In the second example we can choose next parameters: 𝑎=[1,1,2]a=[1,1,2], 𝑏=[1,1,0]b=[1,1,0], 𝑥=[0,0,1]x=[0,0,1].