#include<fstream.h>
#define K 1048576
//using namespace std;
ifstream f1 ("12perm.in");
ofstream f2 ("12perm.out");
int main()
{
long long sol,i,n,a,b,c,d;
f1>>n;
a=1;
b=2;
c=6;
d=12;
for (i=5; i<=n; i++)
{
 sol=d+b+2*c;
 b=c;
 c=d;
 d=sol;
}
if (n>4) f2<<sol%K;
else {if (n==1) f2<<1; if (n==2) f2<<2; if (n==3) f2<<6; if (n==4) f2<<12;}
return 0;
}