数论知识：
1.同余：给定一个正整数m，如果两个整数a和b满足（a-b）能够被m整除，即（a-b）/m为一个整数，即a和b同余。
也可以说成是如果两个整数除以同一个数，若得相同余数，则说明二者同余。
2.欧拉定理：若a与b互质，则a^ϕ(b)≡ 1 (mod b)。
3.乘法逆元：b与m互质，a/b ≡ a * x (mod m),则x是b mod m 乘法逆元，记作b^-1(mod m)。
两边同时乘以b，则变成a ≡ a * x * b(mod m)，即 b * b^-1 ≡ 1 (mod m)，b * x ≡ 1 (mod m)。
4.费马定理： b^(p - 1) ≡ 1(mod p)。p是质数。b于p互质。
5.快速幂O(logk)：反复平方法。
预处理一些数，a^2^0 % p, a^2^1 % p, …… , a^2^logk % k
再用二进制把我们要求的数拆成我们若干个预处理数的乘积：a^k = a^(a^2^x1 + a^2^x2 + …… + a^2^x)。