#include <cstdio>

using namespace std;

int main()
{
    freopen("perm12.in","r",stdin);
    freopen("perm12.out","w",stdout);
    int n,i;
    scanf("%d",&n);
    int a=8,b=8,c=4,s=12,x=4,y=2,mod=(1 << 20) - 1;
    for(i=5;i<=n;i++)
    {
        int cx=x&mod;
        x=b;
        s=(a+b+c)&mod;
        a=(a+b)&mod;
        b=(b+c)&mod;
        c=(cx+y)&mod;
    }
    printf("%d\n",s);
    return 0;
}