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 factorial as f
mod = 10**9 + 7

def P(n,l):
	res = f(n)
	for i in l:
		res//=f(i)
	return res%mod
	
def Func(k,x):
	if len(k)==1:
		return x
	else:
		s = set(k)
		r = []
		r.append(x-len(k))
		d = {}
		for i in s:
			d[i] = 0
		for i in k:
			d[i]+=1
		l1 = list(d.values())
		r.extend(l1)
		res = P(x,r)
		k1 = list(s)
		for i in range(0,len(k1)):
			for j in range(i+1,len(k1)):
				g = list(k)
				g.remove(k1[i])
				g.remove(k1[j])
				g.append(k1[i]*k1[j])
				res += Func(tuple(g),x)
		return res % mod
	

n = int(input())
string = input()
l = string.split()
k = list()
for i in l:
	if i!="1":
		k.append(int(i))
print(Func(tuple(k),n))