Uolevilla on luku $n = p_{1}^{\alpha_1} p_{2}^{\alpha_2} p_{3}^{\alpha_3} \ldots p_{k}^{\alpha_k}$, jossa $p_1 = 2, p_2 = 3, p_3 = 5 \ldots$, eli $p_i$ on i:s alkuluku. Tehtävänäsi on laskea kuinka monta sellaista lukujonoa on olemassa että lukujonon jokainen luku on kokonaisluku ja suurempi kuin $1$, ja lukujonon lukujen tulo on $n$. Ilmoita vastaus modulo $10^9 + 7$.

Syöte

Syötteen ensimmäisellä rivillä on luku $k$, alkulukujen määrä $n$:n alkutekijähajotelmassa. Seuraavalla luvulla on $k$ lukua, $\alpha_1, \alpha_2, \ldots, \alpha_k$.

Tuloste

Tulosta lukujonojen määrä modulo $10^9+7$.

Rajat

• $1 \le k \le 50$
• $1 \le \alpha_i \le 50$

Esimerkki

Syöte:

2
1 1

Tuloste:

3

Tässä $n = 2^1 \cdot 3^1 = 6$. Lukujonot ovat $(2, 3), (3, 2)$ ja $(6)$.

Syöte:

1
2

Tuloste:

2

Tässä $n = 2^2 = 4$. Lukujonot ovat $(2, 2)$ ja $(4)$.

Syöte:

3
3 2 1

Tuloste:

604