#include <stdio.h>
#include <stdlib.h>

#define in "12perm.in"
#define out "12perm.out"

int IM1,IM2,IM3, C;
int n;

int main()
{
    freopen( in, "r", stdin );
    freopen( out, "w", stdout );
    
    scanf( "%d", &n );
    int i;
    if ( n <= 4 )
    {
         if ( n == 1 ) printf( "1\n" );
         else if ( n == 2 ) printf( "2\n" );
         else if ( n == 3 ) printf( "6\n" );
         else if ( n == 4 ) printf( "12\n" );
         exit(0);
    }
    IM1 = 12, IM2 = 6, IM3 = 2; 
    for ( i = 5; i <= n; ++i )
    {
        C = IM1 + IM3 + ((i-2)<<1);
        C %= 1048576;
        IM3 = IM2;
        IM2 = IM1;
        IM1 = C;
    }
    printf( "%d\n", (C%1048576) );
 
    return 0;
}