#include <fstream>
#define M 9999991
using namespace std;
ifstream f("dirichlet.in");
ofstream g("dirichlet.out");
long long a[1000005],i,j,n;
int main()
{
    f>>n;
    a[1]=1;
    a[2]=2;
    for(i=3;i<=n;i++)
    {
        a[i]=1;
        for(j=1;j<=i/2;j++)
        {
            if(j!=i-j) a[i]+=(2*(a[j]*a[i-j])%M)%M;
            else a[i]+=(a[j]*a[i-j])%M;
        }

    }
    g<<a[n];
    return 0;
}