You are given an integer m as a product of integers a_1, a_2, ... a_{n} $(m = \prod_{i = 1}^{n} a_{i})$. 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^9 + 7).


-----Input-----

The first line contains positive integer n (1 ≤ n ≤ 500). The second line contains space-separated integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^9).


-----Output-----

In a single line print a single number k — the number of distinct decompositions of number m into n ordered multipliers modulo 1000000007 (10^9 + 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 = {b_1, b_2, ... b_{n}} such that $m = \prod_{i = 1}^{n} b_{i}$. Two decompositions b and c are considered different, if there exists index i such that b_{i} ≠ c_{i}.

Difficulty: competition

Starter code:

Solutions:
from collections import defaultdict
m = 1000000007

f = [0] * 15001
f[0] = 1
for i in range(1, 15001): f[i] = (f[i - 1] * i) % m

def c(n, k): return (f[n] * pow((f[k] * f[n - k]) % m, m - 2, m)) % m
def prime(n):
    m = int(n ** 0.5) + 1
    t = [1] * (n + 1)
    for i in range(3, m):
        if t[i]: t[i * i :: 2 * i] = [0] * ((n - i * i) // (2 * i) + 1)
    return [2] + [i for i in range(3, n + 1, 2) if t[i]]

p = prime(31650)
s = defaultdict(int)

def g(n):
    for j in p:
        while n % j == 0:
            n //= j
            s[j] += 1
        if j * j > n:
            s[n] += 1
            break

n = int(input()) - 1
a = list(map(int, input().split()))

for i in a: g(i)
if 1 in s: s.pop(1)

d = 1
for k in list(s.values()): d = (d * c(k + n, n)) % m
print(d)


Mod = 1000000007
MAX = 33000
n = int( input() )
A = list( map( int, input().split() ) )

B = [0] * MAX
bePrime = [0] * MAX;
primNum = []
C = []

fac=[1]
for j in range(1, MAX):
    fac.append( fac[-1] * j % Mod )

def calc( M, N ):
    return fac[M] * pow( fac[N] * fac[M-N] % Mod, Mod-2,Mod ) % Mod

for j in range(2, MAX):
    if bePrime[j] == 0: 
        primNum.append( j )
        i = j
        while i < MAX:
            bePrime[i] = 1
            i = i + j

for x in A:
    tmp = x
    for j in primNum:
        while tmp % j == 0:
            tmp /= j
            B[j] += 1
    if tmp > 1:
        C.append( tmp )

ans = 1

for j in range(2,MAX): 
    if B[j] > 0:
        ans = ans * calc( n + B[j] -1 , n - 1 ) % Mod

l = len( C )
for j in range(0, l ):
    num= 0;
    for k in range(0, l ):
        if C[k] == C[j]:
            num = num + 1
            if k > j:
                num = 0
                break
    if num > 0:
        ans = ans * calc( n + num -1, n - 1 ) % Mod

print( str( ans % Mod ) )


from math import sqrt, factorial as f
from collections import Counter
from operator import mul
from functools import reduce


def comb(n, m):
    o = n - m
    if m and o:
        if m < o:
            m, o = o, m
        return reduce(mul, list(range(m + 1, n)), n) // f(o)
    return 1


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 list(c.items()):
        x = x * comb(cnt + n - 1, n - 1) % inf
    print(x)


def __starting_point():
    main()

__starting_point()

# Made By Mostafa_Khaled 
bot = True 
Mod = 1000000007

MAX = 33000

n = int( input() )

A = list( map( int, input().split() ) )



B = [0] * MAX

bePrime = [0] * MAX;

primNum = []

C = []



fac=[1]

for j in range(1, MAX):

    fac.append( fac[-1] * j % Mod )



def calc( M, N ):

    return fac[M] * pow( fac[N] * fac[M-N] % Mod, Mod-2,Mod ) % Mod



for j in range(2, MAX):

    if bePrime[j] == 0: 

        primNum.append( j )

        i = j

        while i < MAX:

            bePrime[i] = 1

            i = i + j



for x in A:

    tmp = x

    for j in primNum:

        while tmp % j == 0:

            tmp /= j

            B[j] += 1

    if tmp > 1:

        C.append( tmp )



ans = 1



for j in range(2,MAX): 

    if B[j] > 0:

        ans = ans * calc( n + B[j] -1 , n - 1 ) % Mod



l = len( C )

for j in range(0, l ):

    num= 0;

    for k in range(0, l ):

        if C[k] == C[j]:

            num = num + 1

            if k > j:

                num = 0

                break

    if num > 0:

        ans = ans * calc( n + num -1, n - 1 ) % Mod



print( str( ans % Mod ) )



# Made By Mostafa_Khaled


MOD = 10**9+7
def SieveOfEratosthenes(n):
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):

        if (prime[p] == True):

            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 1

    l = []
    for p in range(2, n):
        if prime[p]:
            l.append(p)
    return l

def ncr(n, r, p):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,p - 2, p)) % p


primes = SieveOfEratosthenes(31623)
n = int(input())
l = [int(zax) for zax in input().split()]

map = {}
for x in l:
    for p in primes:
        if p>x:
            break
        if x%p==0:
            check = False
            while x%p==0:
                if p in map:
                    map[p]+=1
                else:
                    map[p]=1
                x//=p
    if x!=1:
        if x in map:
            map[x]+=1
        else:
            map[x]=1

count = 1
for x in map:
    count *= ncr(n-1+map[x],n-1,MOD)
    count %= MOD

count %= MOD
print(count)

Mod = 1000000007
 
MAX = 33000
 
n = int( input() )
 
A = list( map( int, input().split() ) )
 
 
 
B = [0] * MAX
 
bePrime = [0] * MAX;
 
primNum = []
 
C = []
 
 
 
fac=[1]
 
for j in range(1, MAX):
 
    fac.append( fac[-1] * j % Mod )
 
 
 
def calc( M, N ):
 
    return fac[M] * pow( fac[N] * fac[M-N] % Mod, Mod-2,Mod ) % Mod
 
 
 
for j in range(2, MAX):
 
    if bePrime[j] == 0: 
 
        primNum.append( j )
 
        i = j
 
        while i < MAX:
 
            bePrime[i] = 1
 
            i = i + j
 
 
 
for x in A:
 
    tmp = x
 
    for j in primNum:
 
        while tmp % j == 0:
 
            tmp /= j
 
            B[j] += 1
 
    if tmp > 1:
 
        C.append( tmp )
 
 
 
ans = 1
 
 
 
for j in range(2,MAX): 
 
    if B[j] > 0:
 
        ans = ans * calc( n + B[j] -1 , n - 1 ) % Mod
 
 
 
l = len( C )
 
for j in range(0, l ):
 
    num= 0;
 
    for k in range(0, l ):
 
        if C[k] == C[j]:
 
            num = num + 1
 
            if k > j:
 
                num = 0
 
                break
 
    if num > 0:
 
        ans = ans * calc( n + num -1, n - 1 ) % Mod
 
 
 
print( str( ans % Mod ) )


# Design_by_JOKER
import math
import cmath

Mod = 1000000007

MAX = 33000

n = int(input())

A = list(map(int, input().split()))

B = [0] * MAX

bePrime = [0] * MAX;

primNum = []

C = []

fac = [1]

for j in range(1, MAX):
    fac.append(fac[-1] * j % Mod)


def calc(M, N):
    return fac[M] * pow(fac[N] * fac[M - N] % Mod, Mod - 2, Mod) % Mod


for j in range(2, MAX):

    if bePrime[j] == 0:

        primNum.append(j)

        i = j

        while i < MAX:
            bePrime[i] = 1

            i = i + j

for x in A:

    tmp = x

    for j in primNum:

        while tmp % j == 0:
            tmp /= j

            B[j] += 1

    if tmp > 1:
        C.append(tmp)

ans = 1

for j in range(2, MAX):

    if B[j] > 0:
        ans = ans * calc(n + B[j] - 1, n - 1) % Mod

l = len(C)

for j in range(0, l):

    num = 0;

    for k in range(0, l):

        if C[k] == C[j]:

            num = num + 1

            if k > j:
                num = 0

                break

    if num > 0:
        ans = ans * calc(n + num - 1, n - 1) % Mod

print(str(ans % Mod))


from math import factorial as f
def primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]
p = primes(31627)
s = [0]*(31623)
s1={}
def factorize(n):
  for i in p:
    if n<=1:
      return 56
    while n%i==0:
      s[p.index(i)]+=1
      n//=i
  if n>1:
    if n in s1:
      s1[n]+=1
    else:
      s1[n]=1
n = int(input())
for i in map(int,input().split()):
  factorize(i)
s = list(filter(lambda a: a != 0, s))
for i in s1.values():
  s.append(i)
ans = 1
for i in s:
  ans*=f(i+n-1)//(f(n-1)*f(i))
print(int(ans)%1000000007)

from math import factorial as f
def primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]
p = primes(31627)
s = [0]*(31623)
s1={}
def factorize(n):
  for i in p:
    if n<=1:
      return 56
    while n%i==0:
      s[p.index(i)]+=1
      n//=i
  if n>1:
    if n in s1:
      s1[n]+=1
    else:
      s1[n]=1
n = int(input())
for i in map(int,input().split()):
  factorize(i)
s = list(filter(lambda a: a != 0, s))
for i in s1.values():
  s.append(i)
ans = 1
for i in s:
  ans*=f(i+n-1)//(f(n-1)*f(i))
print(int(ans)%1000000007)

from math import factorial as f
def primes(n):
    sieve = [True] * n
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i]:
            sieve[i*i::2*i]=[False]*((n-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,n,2) if sieve[i]]
p = primes(31627)
s = [0]*(31623)
s1={}
def factorize(n):
  for i in p:
    if n<=1:
      return 56
    while n%i==0:
      s[p.index(i)]+=1
      n//=i
  if n>1:
    if n in s1:
      s1[n]+=1
    else:
      s1[n]=1
n = int(input())
for i in map(int,input().split()):
  factorize(i)
s = list(filter(lambda a: a != 0, s))
for i in s1.values():
  s.append(i)
ans = 1
for i in s:
  ans*=f(i+n-1)//(f(n-1)*f(i))
print(int(ans)%1000000007)

f=[1]*15001
fi=[1]*15001
a=1
b=1
m=10**9+7
from collections import defaultdict
for i in range(1,15001):
    a*=i
    b*=pow(i,m-2,m)
    a%=m
    b%=m
    f[i]=a
    fi[i]=b
d=defaultdict(int)
def factorize(n): 
    count = 0;  
    while ((n % 2 > 0) == False):  
          
        # equivalent to n = n / 2; 
        n >>= 1;  
        count += 1; 
    if (count > 0): 
        d[2]+=count 
    for i in range(3, int(n**0.5) + 1): 
        count = 0; 
        while (n % i == 0):  
            count += 1; 
            n = int(n / i); 
        if (count > 0): 
            d[i]+=count 
        i += 2; 
  
    # if n at the end is a prime number. 
    if (n > 2): 
        d[n]+=1
ans=1
n=int(input())
l=list(map(int,input().split()))
for i in l:
    factorize(i)
for i in d:
    ans*=(f[d[i]+n-1]*fi[n-1]*fi[d[i]])%m
    ans%=m
print(ans)
        

    


import math
import sys
input=sys.stdin.readline
 
p=(10**9)+7
pri=p
fac=[1 for i in range((10**6)+1)]
for i in range(2,len(fac)):
    fac[i]=(fac[i-1]*(i%pri))%pri
def modi(x):
    return (pow(x,p-2,p))%p;
    
def ncr(n,r):
    x=(fac[n]*((modi(fac[r])%p)*(modi(fac[n-r])%p))%p)%p
    return x;

def prime(x):
    ans=[]
    while(x%2==0):
        x=x//2
        ans.append(2)
    for i in range(3,int(math.sqrt(x))+1,2):
        while(x%i==0):
            ans.append(i)
            x=x//i
    if(x>2):
        ans.append(x)

    return ans;



n=int(input())

z=list(map(int,input().split()))
ans=[]
for i in range(len(z)):
    m=prime(z[i])
    ans.extend(m)
  
ans.sort()
if(ans.count(1)==len(ans)):
    print(1)
    return
cn=[]
count=1
for i in range(1,len(ans)):
    if(ans[i]==ans[i-1]):
        count+=1
    else:
        cn.append(count)
        count=1
cn.append(count)
al=1

for i in range(len(cn)):
    al=al*ncr(n+cn[i]-1,n-1)
    al%=pri
print(al)