#include <bits/stdc++.h>
using namespace std;
const int MOD  = 9999991;
const int VMAX = 1000005;
typedef long long i64;

bool c[2*VMAX];
vector<int> p;

inline void erat(int n){

    int i=0;
    c[0]=1;
    c[1]=1;
    for(int i=4; i<=n; i+=2)
        c[i]=1;
    for(int i=3; i*i<=n; i+=2){
        if(c[i])
            continue;
        for(int j=i*i; j<=n; j+=i+i)
            c[j]=1;
    }
    for(int i=0; i<=n; ++i)
        if(!c[i])
            p.push_back(i);
}

inline int pow(int b, int e){
    int m=1;
    int ans=1;
    while(m<=e){
        if(m&e)
            ans=(1ll*ans*b)%MOD;
        b=(1ll*b*b)%MOD;
        m<<=1;
    }
    return ans;
}

int main(void){
    freopen("dirichlet.in","r",stdin);
    freopen("dirichlet.out","w",stdout);
    int ans,cn,nf,ns,i,t;
    long long j;
    scanf("%d",&nf);
    ns=nf+1;
    cn=2*nf;
    erat(cn+5);
    ans=1;
    for(i=0; i<p.size(); ++i){
        if(p[i]>cn)
            break;
        t=0;
        for(j=p[i]; j<=cn; j*=p[i])
            t+=cn/j-nf/j-ns/j;
        ans=(1ll*ans*pow(p[i],t))%MOD;
    }
    printf("%d",ans);
    return 0;
}