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