#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int f[];
int rule(int n)
{
f[]=;
f[]=;
f[]=;
int k=;
int m=k;
int l=;
for(int i=;i<=n;i++)
{
f[i]=(f[i-]+l)%;
m--;
if(m==)
{
k++;
m=k;
l*=;
l%=;
}
}
return f[n];
}
int main()
{
int t;
while(~scanf("%d",&t))
{
printf("%d\n",rule(t));
}
}
///普通汉诺塔是三层a,b,c,对于四层的汉诺塔可以选择找规律来实现，如果用递归做的话复杂度是o（N^2）肯定是超时的；
///这里举几个例子就能看出规律f[1]=1;f[2]=3;f[3]=5;f[4]=9;f[5]=13;f[6]=17;f[7]=.....;f[i]-f[i-1]分别是1，2，2，4，4，4，4，8，8，8，8，8，8，///8，8(其实规律有点难发现，我是看了别人的博客才知道的-~-！)
