A. О количестве разложений на множители
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Задано целое число m в виде произведения целых чисел a1, a2, ... an . Требуется узнать, сколько существует различных разложений числа m в произведение n упорядоченных целых положительных чисел.

Разложение на n множителей, заданное во входных данных, также должно считаться в ответе. Поскольку ответ может быть очень большим, выведите его по модулю 1000000007 (109 + 7).

Входные данные

В первой строке задано целое положительное число n (1 ≤ n ≤ 500). Во второй строке через пробел заданы целые числа a1, a2, ..., an (1 ≤ ai ≤ 109).

Выходные данные

В единственной строке выведите целое число k — количество различных разложений числа m на n упорядоченных множителей по модулю 1000000007 (109 + 7).

Примеры
Входные данные
1
15
Выходные данные
1
Входные данные
3
1 1 2
Выходные данные
3
Входные данные
2
5 7
Выходные данные
4
Примечание

Во втором примере, чтобы получить разложение числа 2, нужно чтобы одно любое число из трех было равно 2, а остальные равны 1.

В третьем примере возможные варианты разложения на упорядоченные множители — [7,5], [5,7], [1,35], [35,1].

Разложение целого положительного числа m на n упорядоченных множителей — это кортеж целых положительных чисел b = {b1, b2, ... bn}, такой что . Два разложения на упорядоченные множители b и c считаются различными, если существует индекс i, такой что bi ≠ ci.