#include<fstream>
#include<iostream>

using namespace std;

ifstream f("dirichlet.in");
ofstream h("dirichlet.out");
int n, k, a;

int putere(int a, int n)
{
	if (n==0)
		return 1;
	else
		if (n%2==0)
			return putere((a*a), n/2)%9999991;
		else
			return (a*putere((a*a), n/2)%9999991)%9999991;
		

}

int putere2 (int n)
{
	return 1+(putere (3, n-1)-1)/2;
}


int main()
{
	f>>k;
	f.close();
	h<<putere2(k);
	h.close();
	return 0;
}