降幂定理： $a^n\%p=a^{n\%(p-1)}\%p.$
当$p$是素数时成立。
有一点不明白，就是为什么这道题没有保证$k$为质数，为什么还能用降幂定理，是我看错题面了还是本来就是可以用