Problem: You are given a tuple generator f^{(k)} = (f_1^{(k)}, f_2^{(k)}, ..., f_n^{(k)}), where f_i^{(k)} = (a_i ⋅ f_i^{(k - 1)} + b_i) mod p_i and f^{(0)} = (x_1, x_2, ..., x_n). Here x mod y denotes the remainder of x when divided by y. All p_i are primes.

One can see that with fixed sequences x_i, y_i, a_i 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 k ≥ 0) that can be produced by this generator, if x_i, a_i, b_i are integers in the range [0, p_i - 1] and can be chosen arbitrary. The answer can be large, so print the remainder it gives when divided by 10^9 + 7

Input

The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of elements in the tuple.

The second line contains n space separated prime numbers — the modules p_1, p_2, …, p_n (2 ≤ p_i ≤ 2 ⋅ 10^6).

Output

Print one integer — the maximum number of different tuples modulo 10^9 + 7.

Examples

Input

4
2 3 5 7


Output

210


Input

3
5 3 3


Output

30

Note

In the first example we can choose next parameters: a = [1, 1, 1, 1], b = [1, 1, 1, 1], x = [0, 0, 0, 0], then f_i^{(k)} = k mod p_i.

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

Solution (in JAVA):

Solution:
import java.io.*;
import java.math.*;
import java.util.*;

public class A {
	public static void main (String[] args) { new A(); }

	//tough math problem. most of the proof makes sense
	int MOD = (int)1e9+7;
	
	A() {
		Scanner s = new Scanner(System.in);
		System.err.println("");

		int n = s.nextInt();
		int max = 0;
		int[] ps = new int[n];
		for(int i = 0; i < n; i++) {
			ps[i] = s.nextInt();
			if(ps[i] > max) max = ps[i];
		}
		
		boolean[] isPrime = new boolean[max+1];
		int[] lpf = new int[max+1];
		Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false;
		for(int i = 2; i <= max; i++) {
			if(!isPrime[i]) continue;
			lpf[i] = i;
			for(int j = i+i; j <= max; j += i) {
				if(isPrime[j]) {
					isPrime[j] = false;
					lpf[j] = i;
				}
			}
		}
		
		sort(ps);
		int[] maxPows = new int[max+1];
		boolean canAdd1 = false;
		int[] type = new int[n], maxSetBy = new int[max+1];
		
		for(int i = n-1; i >= 0; i--) {
			int val = ps[i];
			if(maxPows[val] == 0) {
				maxPows[val]++;
				maxSetBy[val] = i;
				type[i] = 1;
				continue;
			}
			int[][] pf = getPF(val-1, lpf);
			
			boolean makesProfit = false;
			for(int j = 0; j < pf.length; j++) {
				if(pf[j][1] > maxPows[pf[j][0]]) {
					makesProfit = true;
				}
			}
			if(makesProfit) {
				for(int j = 0; j < pf.length; j++) {
					int pr = pf[j][0];
					if(maxPows[pr] <= pf[j][1]) {
						maxPows[pr] = pf[j][1];
						maxSetBy[pr] = i;
					}
				}
				type[i] = 2;
			}
			else {
				type[i] = -1;
				canAdd1 = true;
			}
		}
		
		int res = 1;
		for(int i = 0; i <= max; i++) {
			res = mult(res, pow(i, maxPows[i]));
		}
		if(!canAdd1){
			//someone might be removable to add 1
			for(int i = 0; i < n; i++) {
				if(type[i] != 2) continue;
				int[][] pf = getPF(ps[i]-1, lpf);
				boolean keep = false;
				for(int j = 0; j < pf.length; j++) {
					int v = pf[j][0];
					if(maxSetBy[v] == i) keep = true;
				}
				if(!keep) {
					canAdd1 = true;
					break;
				}
				
			}
		}
		if(canAdd1) res = (res+1)%MOD;
		
		System.out.println(res);
	}
	
	int pow(int base, int expo) {
		if(expo == 0) return 1;
		if(expo == 1) return base;
		if((expo & 1) == 1) {
			return mult(base, pow(base, expo-1));
		}
		else {
			int ret = pow(base, expo >> 1);
			return mult(ret, ret);
		}
	}
	
	int mult(long a, long b) {
		a *= b;
		if(a >= MOD) a %= MOD;
		return (int)a;
	}
	
	int[][] getPF(int n, int[] lpf) {
		int[][] res = new int[10][2];
		int ptr = 0;
		while(n > 1) {
			int v = lpf[n], cnt = 0;
			while(n%v == 0) {
				cnt++;
				n /= v;
			}
			res[ptr][0] = v; res[ptr][1] = cnt;
			ptr++;
		}
		res = Arrays.copyOfRange(res, 0, ptr);
		return res;
	}
	
	void sort(int[] a) {
		Random rand = new Random();
		int n = a.length;
		for(int i = 0; i < n; i++) {
			int x = rand.nextInt(n);
			int y = rand.nextInt(n);
			int t = a[x]; a[x] = a[y]; a[y] = t;
		}
		Arrays.sort(a);
	}
	
}