给定两个正整数 $d,k$ ，求出最大的正整数 $x$ ，使得 $x|((a+d)^k-a^k)$ 对所有正整数 $a$ 成立。
输入格式
第一行两个正整数 $d,k$ 。
输出格式
一行一个正整数，表示答案。
样例
2 2
4
84623 25861
930853
数据范围与提示
对于所有数据，保证 $1\le d,k\le 10^{100}$ 。
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $d,k\le 10^7$ | $20$ |
| $2$ | $\gcd(d,210)=1$ | $30$ |
| $3$ | $d,k\le 10^{18}$ | $30$ |
| $4$ | $ $ | $20$ |
时间限制：$\texttt{2s}$
空间限制：$\texttt{512MB}$