#include<cstdio>
    using namespace std;
    #define MOD 1048576
    int t[5] , N ;

    int main()
    {
        freopen("12perm.in" , "r" , stdin );
        freopen("12perm.out" , "w" , stdout );
        scanf("%d" , &N );
        t[1] = 1;t[2] = 2; t[3] = 6; t[4] = 12;
        if(N <= 4)
            printf("%d" , t[N]);
        else
        {
            for(int i = 5 ; i <= N ; ++ i)
            {
                t[1] = t[2];t[2] = t[3]; t[3] = t[4];
                t[4] = t[1] + t[3] + 2*(i-2);
                while(t[4] >= MOD)t[4]-=MOD;
            }
            printf("%d" , t[4]);
        }
        return 0;
    }