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: HARD
Tags: Number theory

Combinatorics

Mathematics

Starter code:

Solutions:
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))


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)


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 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()


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)


ans = {}
import math

def factorize(n):
	count = 0
	while (n % 2 > 0) == False:
		n >>= 1
		count += 1
	if count > 0:
		if 2 not in ans:
			ans[2] = count
		else:
			ans[2] += count
	for i in range(3, int(math.sqrt(n)) + 1):
		count = 0
		while n % i == 0:
			count += 1
			n = int(n / i)
		if count > 0:
			if i in ans:
				ans[i] += count
			else:
				ans[i] = count
		i += 2
	if n > 2:
		if n not in ans:
			ans[n] = 1
		else:
			ans[n] += 1
mod = 10 ** 9 + 7

def fact(n):
	f = [1 for x in range(n + 1)]
	for i in range(1, n + 1):
		f[i] = f[i - 1] * i % mod
	return f
f = fact(200000)

def ncr(n, r):
	result = f[n] * pow(f[r], mod - 2, mod) * pow(f[n - r], mod - 2, mod) % mod
	return result
n = int(input())
arr = [int(x) for x in input().split()]
for item in arr:
	factorize(item)
result = 1
for (i, val) in ans.items():
	if val > 0:
		result = result * ncr(val + n - 1, n - 1)
		result = result % mod
print(result)


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 s.values():
	d = d * c(k + n, n) % m
print(d)


import os, sys
from io import BytesIO, IOBase
from collections import Counter

def factor(x, cou):
	while not x % 2:
		x /= 2
		cou[2] += 1
	for i in range(3, int(x ** 0.5) + 1, 2):
		while not x % i:
			x //= i
			cou[i] += 1
	if x != 1:
		cou[x] += 1

def main():
	mod = 10 ** 9 + 7
	fac = [1]
	for ii in range(1, 10 ** 5 + 1):
		fac.append(fac[-1] * ii % mod)
	fac_in = [pow(fac[-1], mod - 2, mod)]
	for ii in range(10 ** 5, 0, -1):
		fac_in.append(fac_in[-1] * ii % mod)
	fac_in.reverse()
	n = int(input())
	a = list(map(int, input().split()))
	cou = Counter()
	for i in a:
		factor(i, cou)
	ans = 1
	for i in cou:
		(a, b) = (cou[i] + n - 1, n - 1)
		ans = ans * fac[a] * fac_in[b] * fac_in[a - b] % mod
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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:
		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 > 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)