#include <bits/stdc++.h>
using namespace std;
const long long UNDEF = -1;
const long long INF = 1e18;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int readInt() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char readCh() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
const long long MAXN = 1e6 + 4;
const long long MAXP = MAXN;
bool sieve_array[MAXP + 1];
long long sp[MAXP + 1];
vector<long long> gpv;
void sieve() {
  for (long long i = 0; i <= MAXP; i++) {
    sieve_array[i] = true;
    sp[i] = INF;
  }
  sieve_array[0] = false;
  sieve_array[1] = false;
  long long lim = sqrt(MAXP) + 1;
  for (long long i = 2; i <= lim; i++) {
    if (sieve_array[i]) {
      for (long long j = i * i; j <= MAXP; j += i) {
        sieve_array[j] = false;
        chkmin(sp[j], i);
      }
    }
  }
  for (long long i = 2; i <= MAXP; i++) {
    if (sieve_array[i]) {
      gpv.push_back(i);
      chkmin(sp[i], i);
    }
  }
}
map<int, int> factorize(long long x) {
  map<int, int> h;
  for (auto &p : gpv) {
    if (x == 1 || p * (long long)p > x) break;
    int cnt = 0;
    while (x % p == 0) {
      x /= p;
      cnt++;
    }
    if (cnt) h[p] = cnt;
  }
  if (x > 1) h[x]++;
  return h;
}
template <class T>
T extgcd(T a, T b, T &x, T &y) {
  for (T u = y = 1, v = x = 0; a;) {
    T q = b / a;
    swap(x -= q * u, u);
    swap(y -= q * v, v);
    swap(b -= q * a, a);
  }
  return b;
}
template <class T>
T mod_inv(T a, T m) {
  T x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}
long long mod_pow(long long a, long long n, long long mod) {
  long long ret = 1;
  long long p = a % mod;
  while (n) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return ret;
}
const long long MAXFACT = 1e5 + 4;
long long fact[MAXFACT + 1], invfact[MAXFACT + 1];
inline long long mul(long long x, long long y) {
  return (x * y) % 1000000007LL;
}
void init() {
  long long got = 1;
  for (long long x = 0; x <= MAXFACT; x++) {
    fact[x] = got;
    got = mul(got, x + 1);
  }
  got = mod_pow(got, 1000000007LL - 2, 1000000007LL);
  for (long long x = MAXFACT; x >= 0; x--) {
    got = mul(got, x + 1);
    invfact[x] = got;
  }
}
long long binom(long long n, long long k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return mul(fact[n], mul(invfact[k], invfact[n - k]));
}
long long starbar(long long stars, long long parts) {
  if (parts == 0) {
    return (stars == 0) ? 1 : 0;
  }
  if (parts <= 0 || stars < 0) return 0;
  return binom(stars + parts - 1, parts - 1);
}
int f(long long x, long long n) {
  if (x == 1 && n == 0)
    return 1;
  else if (n == 0)
    return 0;
  long long ans = 0;
  for (long long y = 1; y <= x; y++) {
    if (x % y == 0) ans += f(y, n - 1);
  }
  return ans % 1000000007LL;
}
int brute(vector<int> v) {
  long long res = 1;
  for (auto &w : v) res *= w;
  return f(res, v.size());
}
int solve(vector<int> v) {
  map<int, int> h;
  int n = v.size();
  for (int i = 0; i < n; i++) {
    int x = v[i];
    auto got = factorize(x);
    for (auto &w : got) {
      h[w.first] += w.second;
    }
  }
  int ans = 1;
  for (auto &w : h) {
    int got = starbar(w.second, n);
    ans = (ans * got) % 1000000007LL;
  }
  return ans;
}
void test() {
  for (int k = 0; k < 10000; k++) {
    long long seed = clock() + rand() + time(0);
    srand(seed);
    int n = rand() % 8;
    vector<int> v;
    for (int x = 1; x <= n; x++) {
      int y = rand() % 100 + 1;
      v.push_back(y);
    }
    int b = brute(v), s = solve(v);
    if (b != s) {
      printf("b:%d s:%d seed:%lld\n", b, s, seed);
      exit(0);
    }
    printf(".");
    fflush(stdout);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  init();
  int n;
  scanf("%d", &n);
  map<int, int> h;
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    auto got = factorize(x);
    for (auto &w : got) {
      h[w.first] += w.second;
    }
  }
  long long ans = 1;
  for (auto &w : h) {
    long long got = starbar(w.second, n);
    ans = (ans * got) % 1000000007LL;
  }
  printf("%d\n", ans);
}

### Prompt

In cpp, your task is to solve the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long UNDEF = -1;
const long long INF = 1e18;
template <typename T>
inline bool chkmax(T &aa, T bb) {
  return aa < bb ? aa = bb, true : false;
}
template <typename T>
inline bool chkmin(T &aa, T bb) {
  return aa > bb ? aa = bb, true : false;
}
static char stdinBuffer[1024];
static char *stdinDataEnd = stdinBuffer + sizeof(stdinBuffer);
static const char *stdinPos = stdinDataEnd;
void readAhead(size_t amount) {
  size_t remaining = stdinDataEnd - stdinPos;
  if (remaining < amount) {
    memmove(stdinBuffer, stdinPos, remaining);
    size_t sz = fread(stdinBuffer + remaining, 1,
                      sizeof(stdinBuffer) - remaining, stdin);
    stdinPos = stdinBuffer;
    stdinDataEnd = stdinBuffer + remaining + sz;
    if (stdinDataEnd != stdinBuffer + sizeof(stdinBuffer)) *stdinDataEnd = 0;
  }
}
int readInt() {
  readAhead(16);
  int x = 0;
  bool neg = false;
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  if (*stdinPos == '-') {
    ++stdinPos;
    neg = true;
  }
  while (*stdinPos >= '0' && *stdinPos <= '9') {
    x *= 10;
    x += *stdinPos - '0';
    ++stdinPos;
  }
  return neg ? -x : x;
}
char readCh() {
  readAhead(16);
  while (*stdinPos == ' ' || *stdinPos == '\n') ++stdinPos;
  char ans = *stdinPos;
  ++stdinPos;
  return ans;
}
const long long MAXN = 1e6 + 4;
const long long MAXP = MAXN;
bool sieve_array[MAXP + 1];
long long sp[MAXP + 1];
vector<long long> gpv;
void sieve() {
  for (long long i = 0; i <= MAXP; i++) {
    sieve_array[i] = true;
    sp[i] = INF;
  }
  sieve_array[0] = false;
  sieve_array[1] = false;
  long long lim = sqrt(MAXP) + 1;
  for (long long i = 2; i <= lim; i++) {
    if (sieve_array[i]) {
      for (long long j = i * i; j <= MAXP; j += i) {
        sieve_array[j] = false;
        chkmin(sp[j], i);
      }
    }
  }
  for (long long i = 2; i <= MAXP; i++) {
    if (sieve_array[i]) {
      gpv.push_back(i);
      chkmin(sp[i], i);
    }
  }
}
map<int, int> factorize(long long x) {
  map<int, int> h;
  for (auto &p : gpv) {
    if (x == 1 || p * (long long)p > x) break;
    int cnt = 0;
    while (x % p == 0) {
      x /= p;
      cnt++;
    }
    if (cnt) h[p] = cnt;
  }
  if (x > 1) h[x]++;
  return h;
}
template <class T>
T extgcd(T a, T b, T &x, T &y) {
  for (T u = y = 1, v = x = 0; a;) {
    T q = b / a;
    swap(x -= q * u, u);
    swap(y -= q * v, v);
    swap(b -= q * a, a);
  }
  return b;
}
template <class T>
T mod_inv(T a, T m) {
  T x, y;
  extgcd(a, m, x, y);
  return (m + x % m) % m;
}
long long mod_pow(long long a, long long n, long long mod) {
  long long ret = 1;
  long long p = a % mod;
  while (n) {
    if (n & 1) ret = ret * p % mod;
    p = p * p % mod;
    n >>= 1;
  }
  return ret;
}
const long long MAXFACT = 1e5 + 4;
long long fact[MAXFACT + 1], invfact[MAXFACT + 1];
inline long long mul(long long x, long long y) {
  return (x * y) % 1000000007LL;
}
void init() {
  long long got = 1;
  for (long long x = 0; x <= MAXFACT; x++) {
    fact[x] = got;
    got = mul(got, x + 1);
  }
  got = mod_pow(got, 1000000007LL - 2, 1000000007LL);
  for (long long x = MAXFACT; x >= 0; x--) {
    got = mul(got, x + 1);
    invfact[x] = got;
  }
}
long long binom(long long n, long long k) {
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return mul(fact[n], mul(invfact[k], invfact[n - k]));
}
long long starbar(long long stars, long long parts) {
  if (parts == 0) {
    return (stars == 0) ? 1 : 0;
  }
  if (parts <= 0 || stars < 0) return 0;
  return binom(stars + parts - 1, parts - 1);
}
int f(long long x, long long n) {
  if (x == 1 && n == 0)
    return 1;
  else if (n == 0)
    return 0;
  long long ans = 0;
  for (long long y = 1; y <= x; y++) {
    if (x % y == 0) ans += f(y, n - 1);
  }
  return ans % 1000000007LL;
}
int brute(vector<int> v) {
  long long res = 1;
  for (auto &w : v) res *= w;
  return f(res, v.size());
}
int solve(vector<int> v) {
  map<int, int> h;
  int n = v.size();
  for (int i = 0; i < n; i++) {
    int x = v[i];
    auto got = factorize(x);
    for (auto &w : got) {
      h[w.first] += w.second;
    }
  }
  int ans = 1;
  for (auto &w : h) {
    int got = starbar(w.second, n);
    ans = (ans * got) % 1000000007LL;
  }
  return ans;
}
void test() {
  for (int k = 0; k < 10000; k++) {
    long long seed = clock() + rand() + time(0);
    srand(seed);
    int n = rand() % 8;
    vector<int> v;
    for (int x = 1; x <= n; x++) {
      int y = rand() % 100 + 1;
      v.push_back(y);
    }
    int b = brute(v), s = solve(v);
    if (b != s) {
      printf("b:%d s:%d seed:%lld\n", b, s, seed);
      exit(0);
    }
    printf(".");
    fflush(stdout);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  sieve();
  init();
  int n;
  scanf("%d", &n);
  map<int, int> h;
  for (int i = 0; i < n; i++) {
    int x;
    scanf("%d", &x);
    auto got = factorize(x);
    for (auto &w : got) {
      h[w.first] += w.second;
    }
  }
  long long ans = 1;
  for (auto &w : h) {
    long long got = starbar(w.second, n);
    ans = (ans * got) % 1000000007LL;
  }
  printf("%d\n", ans);
}

```