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.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

/**
 *
 *
 * @author pttrung
 */
public class C {

    //   public static long x, y, gcd;
    public static int Mod = 1000000007;
    public static PrintWriter out;
    public static int[] x = {0, 0, 1, -1};
    public static int[] y = {1, -1, 0, 0};

    public static void main(String[] args) throws FileNotFoundException {
        Scanner in = new Scanner();
        out = new PrintWriter(System.out);
        //   System.out.println(Integer.MAX_VALUE);
        // PrintWriter out = new PrintWriter(new FileOutputStream(new File("output.txt")));
        int n = in.nextInt();
        int[] data = new int[n];
        for (int i = 0; i < n; i++) {
            data[i] = in.nextInt();
        }
        boolean[] p = new boolean[10000000];
        ArrayList<Integer> list = new ArrayList();
        for (int i = 2; i < p.length; i++) {
            if (!p[i]) {
                list.add(i);
                for (long j = i + i; j < p.length; j += i) {
                    p[(int) j] = true;
                }
            }
        }
        HashMap<Integer, Integer> map = decompose(data, list);

        BigInteger m = BigInteger.valueOf(Mod);
        long result = 1;
        long other = 1;
        for (int i = 1; i <= n - 1; i++) {
            other *= i;
            other %= Mod;
        }
        BigInteger o = BigInteger.valueOf(other);

        for (int k : map.values()) {
            long a = 1;
            for (int i = 1; i <= n + k - 1; i++) {
                a *= i;
                a %= Mod;
            }
            BigInteger u = BigInteger.valueOf(a).mod(m);
            long b = 1;
            for (int i = 1; i <= k; i++) {
                b *= i;
                b %= Mod;
            }
            BigInteger temp = u.multiply((BigInteger.valueOf(b).multiply(o).modInverse(m))).mod(m);
            // System.out.println(temp);
            result *= temp.longValue();
            result %= Mod;
        }
        out.println(result);
        out.close();
    }

    public static HashMap<Integer, Integer> decompose(int[] data, ArrayList<Integer> p) {
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < data.length; i++) {
            int cur = p.get(0);
            int next = 1;
            while (cur * cur <= data[i]) {
                int count = 0;
                while (data[i] % cur == 0) {
                    data[i] /= cur;
                    count++;
                }
                if (count > 0) {
                    if (map.containsKey(cur)) {
                        map.put(cur, map.get(cur) + count);
                    } else {
                        map.put(cur, count);
                    }
                }
                cur = p.get(next++);
            }
            if (data[i] != 1) {
                if (map.containsKey(data[i])) {
                    map.put(data[i], map.get(data[i]) + 1);
                } else {
                    map.put(data[i], 1);
                }
            }
        }
        return map;
    }

    public static Point clock(Point p, int n, int m) {
        Point result = new Point(p.y, n - p.x + 1);
        return result;
    }

    public static Point anti_clock(Point p, int n, int m) {
        Point result = new Point(m - p.y + 1, p.x);
        return result;
    }

    public static int cross(Point a, Point b) {
        int val = a.x * b.y - a.y * b.x;
        return val;
    }

    public static long pow(long a, long b) {
        if (b == 0) {
            return 1;
        }
        if (b == 1) {
            return a;
        }
        long val = pow(a, b / 2);
        if (b % 2 == 0) {
            return val * val;
        } else {
            return val * val * a;
        }
    }

    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);


    }

    public static class Point implements Comparable<Point> {

        int x, y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Point o) {
            if (x != o.x) {
                return x - o.x;
            } else {
                return y - o.y;
            }
        }
    }
//    public static void extendEuclid(long a, long b) {
//        if (b == 0) {
//            x = 1;
//            y = 0;
//            gcd = a;
//            return;
//        }
//        extendEuclid(b, a % b);
//        long x1 = y;
//        long y1 = x - (a / b) * y;
//        x = x1;
//        y = y1;
//
//    }

    public static class FT {

        int[] data;

        FT(int n) {
            data = new int[n];
        }

        public void update(int index, int value) {
            while (index < data.length) {
                data[index] += value;
                index += (index & (-index));
            }
        }

        public int get(int index) {
            int result = 0;
            while (index > 0) {
                result += data[index];
                index -= (index & (-index));
            }
            return result;

        }
    }

    static class Scanner {

        BufferedReader br;
        StringTokenizer st;

        public Scanner() throws FileNotFoundException {
            // System.setOut(new PrintStream(new BufferedOutputStream(System.out), true));
            br = new BufferedReader(new InputStreamReader(System.in));
            //  br = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input.txt"))));
        }

        public String next() {

            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    throw new RuntimeException();
                }
            }
            return st.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }

        public boolean endLine() {
            try {
                String next = br.readLine();
                while (next != null && next.trim().isEmpty()) {
                    next = br.readLine();
                }
                if (next == null) {
                    return true;
                }
                st = new StringTokenizer(next);
                return st.hasMoreTokens();
            } catch (Exception e) {
                throw new RuntimeException();
            }
        }
    }
}
