Look This Editorial!

この問題の制約下では，$x^n-1 \leq 60^{10} = 604661760000000000 \leq 10^{18}$であるので， 64bit整数の範囲内に収まります． よって与えられた整数に対して求める式を実際にシュミレートすればよいです．

また，この問題の制約下では以下の定理(補題)を用いることができるので， それを用いて計算してもよいです．

LTEの補題(Lifting the Exponent lemma)

$p$を素数，$n$を正整数とする．$\mathbf{ord}(n)_{p}$を「$n$を$p$で割り切ることのできる最大の回数」と定義します．

例えば$\mathbf{ord}(9)_{3}=2$，$\mathbf{ord}(16)_{2}=4$，$\mathbf{ord}(10)_{3}=0$ などです．

奇素数$p$に対し，正整数$x,y$が$x \equiv y \mathbf{mod}p$であって$x \not\equiv 0 \mathbf{mod}p$を満たすとき， 任意の正整数$n$に対して以下の等式が成立する．

• $\mathbf{ord}(x^n-y^n)_p = \mathbf{ord}(x-y)_p + \mathbf{ord}(n)_p$

愚直にシュミレートする場合の時間計算量は$O(\mathbf{log}(n)+n\mathbf{log}(x))$， LTEの補題を用いる場合は$O(\mathbf{log}(x)+\mathbf{log}(n))$でどちらも十分高速です． ただしLTEの補題を用いる場合は，$x=1$の場合に注意してください．