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>).
from math import sqrt, factorial
from collections import Counter


def main():
    n = int(input())
    aa = list(map(int, input().split()))
    if n == 1:
        print(1)
        return
    lim = int(sqrt(max(aa)) // 6) + 12
    sieve = [False, True, True] * lim
    lim = lim * 3 - 1
    for i, s in enumerate(sieve):
        if s:
            p, pp = i * 2 + 3, (i + 3) * i * 2 + 3
            le = (lim - pp) // p + 1
            if le > 0:
                sieve[pp::p] = [False] * le
            else:
                break
    sieve[0] = sieve[3] = True
    primes = [i * 2 + 3 for i, f in enumerate(sieve) if f]
    for i, p in enumerate((2, 3, 5, 7)):
        primes[i] = p
    del sieve
    c = Counter()
    for x in aa:
        for p in primes:
            cnt = 0
            while not x % p:
                x //= p
                cnt += 1
            if cnt:
                c[p] += cnt
                if x == 1:
                    break
        if x > 1:
            c[x] += 1
    x, inf = 1, 1000000007
    for p, cnt in c.items():
        x = x * pow(n, cnt, inf) // factorial(cnt) % inf
    print(x)


if __name__ == '__main__':
    main()
