牛客寒假算法基础集训营4 E Applese 涂颜色

题意：

求$2^n, n<=10^{100000}$，答案对1e9+7取模

思路：

费马小定理降幂+快速幂

因为gcd(2,1e9+7)==1

由费马小定理$a^{p-1} \equiv 1(mod \leq p)$

原式=$2^{n%(p-1)}modp,p=1e9+7$

我也不知道为什么用内置函数pow(2,n,p)就直接能过，而手写快速幂就要费马小定理降幂。。

代码：

def fastExpMod(b, e, m):
    result = 1
    while e != 0:
        if (e&1) == 1:
            result *= b
        e >>= 1
        b *= b
        b %= m
        result %= m
    return result
n,m=map(int,input().split())
M = 1000000007
print(fastExpMod(2,n%(M-1),M))