#include <bits/stdc++.h>
#define mod 1048576
using namespace std;

ifstream f ("12perm.in");
ofstream g ("12perm.out");

int n;
long long a[5];
long long b[5];

int main()
{
    f>>n;
    a[1]=1;
    b[1]=0;

    a[2]=2;
    b[2]=0;

    a[3]=a[2]+2;
    b[3]=2;

    a[4]=8;
    b[4]=4;

    for(int i=5;i<=n;++i)
    {
        for(int i=1;i<4;++i)
            a[i]=a[i+1] , b[i]=b[i+1];
        a[4]=a[3]+a[1]+2;
        b[4]=b[3]+a[2];
        a[4]=a[4]%mod;
        b[4]=b[4]%mod;
    }
    g<<(a[4]+b[4])%mod;

    return 0;
}