C. Простые числа и произведение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Введем несколько определений, которые нам понадобятся ниже.

Пусть $$$prime(x)$$$ будет множеством целочисленных простых делителей числа $$$x$$$. Например, $$$prime(140) = \{ 2, 5, 7 \}$$$, $$$prime(169) = \{ 13 \}$$$.

Пусть $$$g(x, p)$$$ будет максимальное число вида $$$p^k$$$, где $$$k$$$ — целое число, такое, что $$$x$$$ делится на $$$p^k$$$. Например:

  • $$$g(45, 3) = 9$$$ ($$$45$$$ делится на $$$3^2=9$$$, но не на $$$3^3=27$$$),
  • $$$g(63, 7) = 7$$$ ($$$63$$$ делится на $$$7^1=7$$$, но не на $$$7^2=49$$$).

Пусть $$$f(x, y)$$$ будет произведением $$$g(y, p)$$$ для всех $$$p$$$, которые содержатся в множестве $$$prime(x)$$$. Например:

  • $$$f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10$$$,
  • $$$f(525, 63) = g(63, 3) \cdot g(63, 5) \cdot g(63, 7) = 3^2 \cdot 5^0 \cdot 7^1 = 63$$$.

Даны числа $$$x$$$ и $$$n$$$. Найдите $$$f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}$$$.

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

Первая строка содержит два целых числа $$$x$$$ и $$$n$$$ ($$$2 \le x \le 10^{9}$$$, $$$1 \le n \le 10^{18}$$$) — числа, которые используются в формулах.

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

Выведите ответ.

Примеры
Входные данные
10 2
Выходные данные
2
Входные данные
20190929 1605
Выходные данные
363165664
Входные данные
947 987654321987654321
Выходные данные
593574252
Примечание

В первом примере $$$f(10, 1) = g(1, 2) \cdot g(1, 5) = 1$$$, $$$f(10, 2) = g(2, 2) \cdot g(2, 5) = 2$$$.

Во втором примере само число равно $$$1.597 \cdot 10^{171}$$$. Убедитесь вывести ответ по модулю $$$(10^{9} + 7)$$$.

В третьем примере будьте осторожны с переполнением.