#include<fstream>
using namespace std;
long long gauss(long long prev)
{
    return (prev*(prev+1))/2;
}
int main()
{
    long long n,prev=1,i;
    ifstream q("dirichlet.in");
    ofstream w("dirichlet.out");
    q>>n;
    for(i=2;i<=n;i++)
    {
        prev=((prev+gauss(prev))%9999991);
    }
    w<<prev;
    return 0;
}