Public Judge

pjudge

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
统计

给定两个正整数 $d,k$ ,求出最大的正整数 $x$ ,使得 $x|((a+d)^k-a^k)$ 对所有正整数 $a$ 成立。

输入格式

第一行两个正整数 $d,k$ 。

输出格式

一行一个正整数,表示答案。

样例一

input

2 2

output

4

样例二

input

84623 25861

output

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}$