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