#include <fstream>
using namespace std;
int     st[20000], n, nrsol=0;

int DeterminareMaxim(int k)
{  int maxim=0,i;
    for(i=1;i<=k;i++)
        if (st[i]>maxim) maxim=st[i];
    return maxim;
}


void Back(int k)
{  int i;
   for(i=1;i<=DeterminareMaxim(k-1)+1;i++)
      { st[k]=i;
    if (k==n) nrsol=(nrsol+1)%9999991;
    else Back(k+1);
     }
}

int main()
{
 ifstream f("dirichlet.in");
 ofstream g("dirichlet.out");
  f>>n;
  Back(1);
  g<<nrsol%9999991;
  return 0;
}