题解 | 涂颜色快速幂+大整数取模+费马小定理

#include<iostream>
#include<algorithm>

using namespace std;

int mod(string s) {
    long long remainder = 0;
    for (char c:s) remainder = (remainder * 10 + c - '0') % 1000000006;
    return remainder;
}

int main() {
    string s;
    cin >> s;
    int a = mod(s);
    long long ans = 1, base = 2;
    while (a) {
        if (a & 1) ans = ans * base % 1000000007;
        base = base * base % 1000000007;
        a >>= 1;
    }
    cout << ans;
    return 0;
}