Số nguyên tố và phép nhân

Với số nguyên dương $x$, gọi $\text{prime}(x)$ là tập các ước nguyên tố của $x$. Ví dụ $\text{prime}(140)=\{2,5,7\}$, $\text{prime}(169)=\{13\}$.

Với số nguyên tố $p$, gọi $g(x,p)$ là luỹ thừa $p^k$ lớn nhất sao cho $x$ chia hết cho $p^k$ ($k$ nguyên không âm). Ví dụ $g(45,3)=9$ (vì $45$ chia hết cho $3^2=9$ nhưng không chia hết cho $3^3=27$), $g(63,7)=7$.

Với hai số nguyên dương $x,y$, gọi $f(x,y)$ là tích của $g(y,p)$ trên tất cả $p\in \text{prime}(x)$. Ví dụ:

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

Cho hai số nguyên $x$ và $n$. Hãy tính

$$f(x,1)·f(x,2)·\dots ·f(x,n)mod({10}^9+7).$$

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $x$ và $n$.

Dữ liệu ra

In ra một số nguyên là giá trị của biểu thức lấy theo modulo ${10}^9+7$.

Ràng buộc

• $2\le x\le {10}^9$
• $1\le n\le {10}^{18}$

Ví dụ