费马小定理
题意：求s1+s2+s3+...+sn;si表示n划分i个数的n的划分的个数,如n=4,则s1=1,s2=3
利用隔板定理可知，就是求（2^n-1）%mod-----Y
现在已知 (2^mod-1)%mod = 1,所以 Y = 2^( (n%(mod-1) -1 +mod)%mod )%mod
证明（ 定理：a^(p-1)==1%p,gcd(a,p)==1 ）：
(http://www.cnitblog.com/luckydmz/archive/2008/06/03/39458.html)
构造模p的完全剩余系P = {0，1, 2, … ,p-1}，
因为gcd(a, p) = 1，所以A= {0*a, 1*a, 2*a, … ,(p-1)*a}也是模p的一个完全剩余系。
就是说P和A在模p意义下是相等的。
因为0 ≡ 0a (mod p)，所以 P-{0} 与 A-{0*a}在模p意义下是相等的。
记P'=P-{0},A'=A-{0*a}
令W = πP' = 1 * 2 * 3 * 4 … * (p-1)，Y = πA' = a * 2a *3a * 4a * …(p-1)a = W*a^(p-1) //π表示连乘积
有，W ≡ Y (mod p)
即，W ≡ W*a^(p-1) (mod p)
又因为，(W, p) = 1
则有，1 ≡ a^(p-1) (mod p)
/*
费马小定理
题意：求s1+s2+s3+...+sn;si表示n划分i个数的n的划分的个数,如n=4,则s1=1,s2=3
利用隔板定理可知，就是求（2^n-1）%mod-----Y
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b))
const int maxn = ;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-;
const int64 mod = +; int64 Fast_Pow( int64 a,int64 n,int64 mod ){
int64 res = ;
while( n>= ){
if( n& ){
res = res*a%mod;
}
a = a*a%mod;
n >>= ;
}
return res%mod;
} int64 GetNum( char str[],int64 mod ){
int64 res = ;
int len = strlen( str );
for( int i=;i<len;i++ ){
res = (res*+str[i]-'')%mod;
}
return res;
} int main(){
char str[ maxn ];
while( scanf("%s",str)!=EOF ){
int64 n = GetNum( str,mod- );
printf("%I64d\n",Fast_Pow( ,(n-+mod)%mod,mod ));
}
return ;
}