HDU 4704 Sum（隔板原理+组合数求和公式+费马小定理+快速幂）

#include<iostream>
#include<string.h>
using namespace std;
typedef long long LL;
#define mod 1000000007
char s[1000000];

LL bp(LL a,LL b){
	LL ans=1;
	LL res=a;
	while(b){
		if(b&1){
			ans=ans*res;
			ans%=mod;
		}
		res=res*res;
		res%=mod;
		b>>=1;
	}
	return ans;
}

int main(){
	LL n;
	while(~scanf("%s",s)){
		LL t=strlen(s);
		LL k=s[0]-'0';
		for(LL i=1;i<t;i++){
			k=(k*10+(s[i]-'0'))%(mod-1);
		}
		k-=1;
		printf("%lld\n",bp(2,k));
	}
}