Введем несколько определений, которые нам понадобятся ниже.
Пусть \(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)}\).
Примечание
В первом примере \(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)\).
В третьем примере будьте осторожны с переполнением.