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