费马小定理 快速幂

题意求一个超级大的数N，分成i种方案的总和，这个有个隔板法的公式，结果为2^(n-1)-1，因为n太大用费马小定理 费马小定理，a^(p-1)=1(%p)
当p和a互质的时候，把n%（p-1）和n等效。

#include<iostream>
#include<string>
using namespace std;
const	int mod=1e9+7;
int qs(int a,int b,int n)
{
	int res=1;
	while(b)
	{
		if(b&1)		res=(long long )res*a%n;
		a=(long long)a*a%n;
		b>>=1;
				
	}
	return res;
}
long long convert(string s)
{
	long	long ans=0;
	for(int i=0;i<s.size();i++)
	ans=(ans*10+(s[i]-'0'))%(mod-1);
	return ans;
}
int main()
{
	string s;
	while(cin>>s)
	{
		long long n=convert(s);
		cout<<qs(2,n-1,mod)<<endl;
	}
}