2019计蒜之道初赛第3场-阿里巴巴协助征战SARS 费马小定理降幂

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int P=1e9+7;
typedef long long LL;
char s[N];

LL power(LL x,LL p) {
    LL ret=1;
    for (;p;p>>=1) {
        if (p&1) ret=(ret*x)%P;
        x=(x*x)%P;
    }
    return ret;
}

int main()
{
    while (scanf("%s",s) && s[0]!=‘0‘) {
        LL n=0;
        for (int i=0;i<strlen(s);i++) {
            n=n*10%(P-1)+(s[i]-‘0‘); n%=(P-1);
        }
        n=((n-1)+(P-1))%(P-1);
        printf("%d\n",(power(2,n)+power(4,n))%P);
    }
    return 0;
}