#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

ifstream fin("dirichlet.in");
ofstream fout("dirichlet.out");

const int MOD = 9999991;

class big_int{
    public:
        vector<int>cifre;

        big_int(){
            cifre.push_back(1);
            cifre.push_back(1);
        }


        void afis_num(){
            for(int i=cifre[0];i>=1;i--){
                cout<<cifre[i];
            }
            cout<<'\n';
        }

        void multiplication(int val){
            int carry = 0;
            for(int i=1;i<=cifre[0];i++){
                carry = carry + cifre[i] * val;
                cifre[i] = carry%10;
                carry/=10;
            }
            while(carry!=0){
                cifre[0]++;
                cifre.push_back(carry%10);
                carry/=10;
            }
        }

        void division(int val){
            int carry = 0;
            for(int i=cifre[0];i>=1;i--){
                carry = carry * 10 + cifre[i];
                cifre[i] = carry/val;
                carry %= val;
            }
            while(cifre[cifre[0]] == 0 &&cifre[0]>1){
                cifre.pop_back();
                cifre[0]--;
            }
        }
};


void big_catalan(int n){
    big_int Cat;
    for(int i=1;i<=n;i++){
        Cat.multiplication(2*(2*i-1));
        Cat.division(i+1);
    }
    Cat.afis_num();
}

int expo_r(int val,int putere){
    int raspuns = 1;
    while(putere>0){
        if(putere%2==1){
            raspuns = 1LL * raspuns * val % MOD;
        }
        val = 1LL * val*val  % MOD;
        putere/=2;
    }
    return raspuns;
}

long long  catalan(int n){
    long long c = 1;
    for(int i=1;i<=n;i++){
        c = 2LL * c * (2*i - 1) % MOD * expo_r(i+1, MOD-2) % MOD;
    }
    return c;
}

int main(){
    int n;
    cin>>n;
    cout<<catalan(n);

    return 0;
}