У Айрата есть число n, представленное в виде разложения на m простых множителей pi, то есть n = p1·p2·...·pm. Айрат получил секретную информацию, что произведение всех делителей n по модулю 109 + 7 — пароль от секретной базы данных. Теперь осталось только вычислить это значение.
Выходные данные
Выведите одно число — произведение всех делителей числа n, вычисленное по модулю 109 + 7.
Примечание
В первом примере n = 2·3 = 6. Делителями числа 6 являются 1, 2, 3 и 6, их произведение 1·2·3·6 = 36.
Во втором примере 2·3·2 = 12. Делители числа 12 — 1, 2, 3, 4, 6 и 12. 1·2·3·4·6·12 = 1728.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 3
|
36
|
|
2
|
3
2 3 2
|
1728
|