#P1030G. Linear Congruential Generator
Linear Congruential Generator
Description
You are given a tuple generator , where and . Here denotes the remainder of when divided by . All are primes.
One can see that with fixed sequences , , the tuples starting from some index will repeat tuples with smaller indices. Calculate the maximum number of different tuples (from all for ) that can be produced by this generator, if , , are integers in the range and can be chosen arbitrary. The answer can be large, so print the remainder it gives when divided by
The first line contains one integer () — the number of elements in the tuple.
The second line contains space separated prime numbers — the modules ().
Print one integer — the maximum number of different tuples modulo .
Input
The first line contains one integer () — the number of elements in the tuple.
The second line contains space separated prime numbers — the modules ().
Output
Print one integer — the maximum number of different tuples modulo .
Samples
Note
In the first example we can choose next parameters: , , , then .
In the second example we can choose next parameters: , , .