费马小定理—— HDU4704 Sum

费马小定理：

假如p是素数，且a与p互质，那么a^(p-1) = 1 (mod p)。

---

应用:

说明了模素数的指数是有循环节的，且循环节长度为p-2，减少运算量

2^n%m == ( 2^(n%(m-1))*    2^(n/(m-1)*(m-1))    )%m == (2^(n%(m-1)))%m * ((2^k)^(m-1))%m == (2^(n%(m-1)))%m * 1 == (2^(n%(m-1)))%m;

HDU4704 Sum

//求2^(n-1); n很大

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
const int INF_INT  = 0x3f3f3f3f;
const ll INF_LL  = 1e18;
const int MOD=1e9 + 7;


string s;
ll pow_mod(ll a,ll n,ll m)
{
    ll re = 1;
    while(n>0)
    {
        if(n%2)
        {
            re = re*a%m;
        }
        a = a*a%m;
        n/=2;
    }
    return re;
}


int main()
{
    ios_base::sync_with_stdio(false);
//    freopen("data.txt","r",stdin);
    while(cin>>s)
    {
        ll sum = 0;
        for(int i=0;i<s.size();i++)
        {
            sum = (sum*10+s[i]-'0')%(MOD-1);
        }
        cout << pow_mod(2,sum-1,MOD)<<endl;
    }

}