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