#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=,mod=;

int jc[mod+],jcn[mod+];

char ch[xn];

struct N{int a[xn];}n;

ll pw(ll a,int b)

{

  ll ret=;

  for(;b;b>>=,a=(a*a)%mod)

      if(b&)ret=(ret*a)%mod;

  return ret;

}

int md(N x)

{

  for(int i=x.a[];i>;i--)

    x.a[i-]+=(x.a[i]%mod)*,x.a[i]=;

  return x.a[]%mod;//%mod

}

int C(int n,int m){return ((ll)jc[n]*jcn[m])%mod*jcn[n-m]%mod;}

int Lucas(N n,int m)

{

  if(n.a[]<=&&n.a[]<)return ;

  int p=md(n);

  return C(p,m%mod)%mod;

}

int main()

{

  scanf("%s",ch+); int l=n.a[]=strlen(ch+);

  for(int i=;i<=l;i++)n.a[i]=ch[l-i+]-'';

  n.a[]+=;

  for(int i=;i<=l;i++)n.a[i+]+=n.a[i]/,n.a[i]%=;

  if(n.a[l+])n.a[]++;

  jc[]=;

  for(int i=;i<mod;i++)jc[i]=(ll)jc[i-]*i%mod;

  jcn[mod-]=pw(jc[mod-],mod-);

  for(int i=mod-;i>=;i--)jcn[i]=(ll)jcn[i+]*(i+)%mod;

  printf("%d\n",Lucas(n,));

  return ;

}