Given two positive integers $d$ and $k$, find the largest positive integer $x$ such that $x \mid ((a+d)^k - a^k)$ holds for all positive integers $a$.
Input
The first line contains two positive integers $d$ and $k$.
Output
Output a single positive integer representing the answer.
Examples
Input 1
2 2
Output 1
4
Input 2
84623 25861
Output 2
930853
Constraints
For all test cases, $1 \le d, k \le 10^{100}$.
| Subtask ID | Special Property | Score |
|---|---|---|
| $1$ | $d, k \le 10^7$ | $20$ |
| $2$ | $\gcd(d, 210) = 1$ | $30$ |
| $3$ | $d, k \le 10^{18}$ | $30$ |
| $4$ | $20$ |