You are given an integer m as a product of integers a1, a2, ... an <image>. Your task is to find the number of distinct decompositions of number m into the product of n ordered positive integers.

Decomposition into n products, given in the input, must also be considered in the answer. As the answer can be very large, print it modulo 1000000007 (109 + 7).

Input

The first line contains positive integer n (1 ≤ n ≤ 500). The second line contains space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output

In a single line print a single number k — the number of distinct decompositions of number m into n ordered multipliers modulo 1000000007 (109 + 7).

Examples

Input

1
15


Output

1


Input

3
1 1 2


Output

3


Input

2
5 7


Output

4

Note

In the second sample, the get a decomposition of number 2, you need any one number out of three to equal 2, and the rest to equal 1.

In the third sample, the possible ways of decomposing into ordered multipliers are [7,5], [5,7], [1,35], [35,1].

A decomposition of positive integer m into n ordered multipliers is a cortege of positive integers b = {b1, b2, ... bn} such that <image>. Two decompositions b and c are considered different, if there exists index i such that bi ≠ ci.

import java.util.*;
import java.io.*;
public class A {
	public static long time = 0;
	public static void main(String[] args) throws Exception {
		time = System.currentTimeMillis();
		
		IN = System.in;
		OUT = System.out;
		in = new BufferedReader(new InputStreamReader(IN));
		out = new PrintWriter(OUT, FLUSH);
		solveOne();
		out.flush();
	}
	
	
	public static long[] primeFactors = new long[(int)(1e7) * 2];
	public static int factorSize = 0;
	public static void solveOne() throws Exception {
		int n1 = ni();
		for (int i = 0 ; i  < n1; i++){
			long cur = ni();
			for (long j = 2; j * j <= cur;j ++){
				for (;;){
					if (cur % j == 0){
						primeFactors[factorSize++] = j;
						cur /= j;
					}
					else break;
				}
			}
			if (cur > 1l){
				primeFactors[factorSize++] = cur;
			}
		}
		
		Arrays.sort(primeFactors, 0 , factorSize);
//		px(Arrays.copyOf(primeFactors, factorSize));
		
		ArrayList<Integer> counts = new ArrayList<>();
		int curCount = -1;
		for (int i = 0 ; i < factorSize; i++){
			if (i == 0 || primeFactors[i] != primeFactors[i - 1]){
				if (curCount >= 0) counts.add(curCount);
				curCount = 1;
			}
			else {
				curCount++;
			}
		}
		if (curCount >= 0) counts.add(curCount);
//		px(counts);
		long fin = 1;
		for (long e: counts){
			long cur = modChoose(e + n1 - 1, n1 - 1);
//			px("asdf", e+ n1 - 1, n1 - 1, cur);
			fin *= cur;
			fin %= MOD;
		}
		pn(fin);
	}
	static long modChoose(long n1, long k1){
		if (k1 > n1 - k1)  return modChoose(n1, n1 - k1);
		long top = n1;
		long bot = 1;
		long fin = 1;
		for (int i = 0; i < k1; i++){
			fin *= top;
			fin %= MOD;
			fin *= Modz.modInverse(bot, MOD);
			fin %= MOD;
			top--;
			bot++;
		}
		return fin;
	}
	static long MOD = 1000000007;
	
	public static void solveTwo() throws Exception {
		
	}
	
	public static void solveThree() throws Exception {
		
	}
	
	public static BufferedReader in;
	public static StringTokenizer st;
	public static InputStream IN;
	public static OutputStream OUT;
	public static String nx() throws Exception {
		for (;st == null || !st.hasMoreTokens();){
			String k1 = in.readLine();
			if (k1 == null) return null;
			st = new StringTokenizer(k1);
		}
		return st.nextToken();
	}
	public static int ni () throws Exception {
		return Integer.parseInt(nx());
	}
	public static long nl() throws Exception{
		return Long.parseLong(nx());
	}
	public static double nd() throws Exception{
		return Double.parseDouble(nx());
	}
	public static void px(Object ... l1){
		System.out.println(Arrays.deepToString(l1));
	}
	public static boolean FLUSH = false;
	public static PrintWriter out;
	public static void p(Object ... l1){
		for (int i = 0; i < l1.length; i++){
			if (i != 0) out.print(' ');
			out.print(l1[i].toString());
		}
	}
	public static void pn(Object ... l1){
		for (int i = 0; i < l1.length; i++){
			if (i != 0) out.print(' ');
			out.print(l1[i].toString());
		}
		out.println();
	}
	
	public static void pn(Collection l1){
		boolean first = true;
		for (Object e: l1){
			if (first) first = false;
			else out.print(' ');
			out.print(e.toString());
		}
		out.println();
	}
	
	private static 
 class Modz {
		public static long mod(long n1, long mod) {
			long fin = n1 % mod;
			if (fin < 0) fin += mod;
			return fin;
		}
		public static long modInverse(long n1, long mod){
			long top = mod;
			long bot = n1;
			
			long bot1 = 0;
			long bot2 = 1;

			for (;;){
				if (bot == 1) break;
				long times = top / bot;
				long rmd = top % bot;
				long bot3 = bot1 - times * bot2;
				bot1 = bot2;
				bot2 = bot3;
				top = bot;
				bot = rmd;
			}

			return Modz.mod(bot2, mod);
		}
	}

}
