You are given an integer $$N$$ and a value $$k$$. You need to find a minimum number $$X$$ which when multiplied to $$N$$ results in the value of $$N ^ {1 / k}$$ as an integer. 

For example let $$N = 6$$ and $$K = 2$$ , then the answer will be $$6$$ because $$6 \times 6 = 36$$ and if we calculate $$36 ^{1/2}$$ it is equal to $$6$$ which is an integer.

Input
The first line contains two space-separated values $$N$$ and $$k$$ as input.

Output
Print the minimum number $$X$$ modulo $$10^9 + 7$$

Constraints
$$1 \le N \le 10^{12}$$
$$1 \le k \le 10^{12}$$