我就是点分治过的，复杂度 $O(nk\log n)$

qpow 不要用快速幂，提前打表即可，相信自己的常数，我跑了 7s，稳过的