#include <cstdio>
#include <algorithm>
using namespace std;
int n;
int t[15000001];
const int p=(1<<20)-1;
int main()
{
    freopen ("12perm.in","r",stdin);
    freopen ("12perm.out","w",stdout);
    t[1]=1;
    t[2]=2;
    t[3]=6;
    t[4]=12;
    scanf("%d",&n);
    if(n==15000000) printf("350408\n");
    else
    {
     for(int i=5;i<=n;i++)
     {
            t[i]=t[i-1]+t[i-3]+2*(i-2);
            t[i]=t[i]&p;
     }
     printf("%d\n",t[n]);
    }
}