# include <cstdio> # include <cstring> # include <algorithm>
using namespace std;
const int N=99,M=170,mo=1e9;
typedef long long LL;
char c[N];
int tot;
struct num { int w,a[M]; }f[N+5][N+5],ans,n,p,t,s[N+5],g[N+5][N+5];
num operator + (const num &a,const num &b) { t.w=max(a.w,b.w); //t.a[1]=0; memset(t.a,0,sizeof(t.a)); for (int i=1;i<=t.w;i++) { t.a[i]+=a.a[i]+b.a[i]; if (t.a[i]>=mo) { t.a[i+1]=1; t.a[i]-=mo; }//else t.a[i+1]=0; } if (t.a[t.w+1]>0) t.w++; //memset(t.a+t.w+1,0,sizeof(t.a+t.w+1)); return t; }
num operator * (const num &a,const num &b) { memset(t.a,0,sizeof(t.a)); for (int i=1;i<=a.w;i++) { for (int j=1;j<=b.w;j++) { t.a[i+j]+=(t.a[i+j-1]+(LL)a.a[i]*b.a[j])/mo; t.a[i+j-1]=(t.a[i+j-1]+(LL)a.a[i]*b.a[j])%mo; } } for (t.w=a.w+b.w;t.w>1 && t.a[t.w]==0;t.w--); return t; }
int main() { freopen("data.out","w",stdout); scanf("%s",c+1); int l=strlen(c+1); n.w=l/9+1; for (int i=1;i<=l;i++) { int j=(l-i)/9; n.a[j+1]=n.a[j+1]*10+c[i]-48; } f[0][0].w=f[0][0].a[1]=1; for (int i=1;i<=N;i++) { for (int j=0;j<i;j++) { for (int k=0;k<=j;k++) { f[i][j]=f[i][j]+f[i-1][k]*f[i-1-k][j-k]; } } f[i][i].w=f[i][i].a[1]=1; } tot=0; for (int i=0;i<=N;i++) { if (n.a[1]&1) { tot++; if (tot==1) { for (int j=0;j<=i;j++) g[1][j]=f[i][j]; }else { for (int j=0;j<=i;j++) { for (int k=0;k<=j;k++) { g[tot][j]=g[tot][j]+g[tot-1][k]*f[i-k][j-k]; } } } } int r=0; for (int j=n.w;j;j--) { int t=n.a[j]; n.a[j]=((LL)r*mo+t)/2; r=((LL)r*mo+t)%2; } } for (int i=0;i<=N;i++) ans=ans+g[tot][i]; printf("%d",ans.a[ans.w]); for (int i=ans.w-1;i;i--) { for (int j=1e8;j;j/=10) { printf("%d",ans.a[i]/j); ans.a[i]%=j; } } printf("\n"); return 0; }