# include <cstdio>

using namespace std;


long long sol[1000005], sum[1000005];
int n, k, ok, ct;
void back(int k)
{int i;
     
     if (k == n + 1)
     {  
        ok = 0;
        
        for (i = 1; i <= n; i++)
        sum[i] = 0;
        
        for (i = 1; i <= n; i++)
        {
            sum[i] = sum[i - 1] + sol[i];
            //if (sol[i]) ok = 1;
            }
            
        if (sum[n] == n)
        for (i = 1; i <= n; i++)
              if (sum[i] <= i) ok = 1;
                         else {ok = 0; break;}
                 //printf("%d ",sol[i]);
                 
                 if (ok) ct++;
        
        }
              
     else 
     {
          sol[k] = -1;
          while (sol[k] < n)
          {
                sol[k]++;
                back(k + 1);
                }
          }
}

int main()
{
    
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);
    
    scanf("%d",&n);
    
    back(1);
    
    printf("%d",ct % 9999991);
    
return 0;
}