#include<algorithm>
#define BAZ 1000000
#define DIM 5001
using namespace std;
long long n,b[DIM],sol[DIM],aux[DIM];
void inm2(){
	long long i;
	long long t;
	for(i=1,t=0; i<=sol[0]||t; t/=BAZ,++i)
		sol[i]=(t+=sol[i]*n)%BAZ;
	sol[0]=i-1;}
void inm1(){
    long long i,j;
    long long t;
    memset(aux,0,sizeof(aux));
    for(i=1; i<=b[0]; ++i){
        for(j=1,t=0; j<=b[0]||t; t/=BAZ,++j)
			aux[i+j-1]=(t+=aux[i+j-1]+b[i]*b[j])%BAZ;
        if(i+j-2>aux[0])
            aux[0]=i+j-2;}
    memcpy(b,aux,sizeof(aux));}
void inm0(){
    long long i,j;
    long long t;
    memset(aux,0,sizeof(aux));
    for(i=1; i<=b[0]; ++i){
        for(j=1,t=0; j<=sol[0]||t; t/=BAZ,++j)
            aux[i+j-1]=(t+=aux[i+j-1]+b[i]*sol[j])%BAZ;
        if(i+j-2>aux[0])
            aux[0]=i+j-2;}
    memcpy(sol,aux,sizeof(aux));}
void pow(){
    long long p;
	for(p=n*n; p; p>>=1){
		if(p&1)
			inm0();
		inm1();}}
void solve(){
	long long i,j;
	scanf("%lld",&n);
	b[0]=sol[0]=sol[1]=1;
	b[1]=2;
	pow();
	//inm2();
	for(printf("%lld",sol[sol[0]]),i=sol[0]-1; i>0; --i){
		printf("%.6lld",sol[i]);}}
int main(){
    freopen("patrate2.in","r",stdin);
    freopen("patrate2.out","w",stdout);
    solve();
    return 0;}