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