涂颜色

/*
规定左右相邻两格的颜色不能相同，一行2种涂色方案，n行就是2的n次方种涂色方案
n已经大到无法用已有数据来存储 2^n只会更大 需要对指数n进行模运算
费马小定理：
a^b  mod MOD = a^( b mod (MOD-1) )  mod MOD（MOD为质数）1e9+7为质数
指数取模的依据：a^(MOD-1) ≡ 1  (mod MOD) 只要MOD是质数，a 的 (MOD−1) 次方 mod MOD，结果一定是 1
*/
#include <iostream>
#include <string>
using namespace std;

int MOD = 1e9+7;

//输入的大整数对 MOD-1 取模
int modexp(string s){
    long long ans=0;
    for(int i=0;i<s.length();i++){
        ans = (ans*10 + s[i]-'0') % (MOD-1);
    }
    return ans;
}

//快速幂对p取模
long long fastpowmod(int base,int exp,int p){
    if(exp==0) return 1;
    long long temp=fastpowmod(base, exp/2, p) % p;
    if(exp%2==0) return temp*temp % p;
    else return base*temp*temp % p;
} //temp 和返回全都要改成 long long 不然数据溢出结果不对

int main() {
    string n;
    cin>>n;
    int exp = modexp(n);
    cout<<fastpowmod(2,exp,MOD);
}