You are given an integer *m* as a product of integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ... *a*<sub class="lower-index">*n*</sub> <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/cf060eec22f7a6ddd13992efe2ebf6d08fde945a.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 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 (10<sup class="upper-index">9</sup> + 7).
The first line contains positive integer *n* (1 ≤ *n* ≤ 500). The second line contains space-separated integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>).
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> fact(int n) {
    vector<int> f;
    for (long long i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            f.push_back(i);
            n /= i;
        }
    }
    if (n != 1) {
        f.push_back(n);
    }
    return f;
}
int32_t main() {
    int n;
    cin >> n;
    int s = 0;
    vector<int> f;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        for (auto i : fact(x)) {
            f.push_back(i);
            s = max(s, i + 1);
        }
    }
    vector<int> cnt(s);
    for (auto i : f) {
        cnt[i]++;
    }
    int ans = 1;
    for (auto k : cnt) {
        if (k == 0) {
            continue;
        }
        int sum = 1;
        for (int i = n; i < n + k; i++) {
            sum *= i;
        }
        ans *= sum;
    }
    cout << ans;
    return 0;
}