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