#include <cstdio>


#define MOD 1048575
#define Nmax 15000005

using namespace std;
int A[Nmax],B[Nmax];

int main()
{
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);


    A[1] = 1;  B[1] = 0;
    A[2] = 2;  B[2] = 0;
    A[3] = 4;  B[3] = 2;
    A[4] = 8;  B[4] = 4;
    A[5] = 12; B[5] = 8;
    A[6] = 18; B[6] = 16;
    A[7] = 28; B[7] = 28;
    A[8] = 42; B[8] = 46;


    int N;
    scanf("%d",&N);
    if(N <= 8)
    {
        printf("%d\n",A[N]+B[N]);
        return 0;
    }
    ///A[i] = A[i-1] + A[i-3] + 2
    ///B[i] = B[i-1] + A[i-2]

    int A1,A2,A3,AA;
    int B1,B2,BB;

    A1 = A[8];
    A2 = A[7];
    A3 = A[6];
    B1 = B[8];
    B2 = B[7];

    for(int i = 9; i <= N; ++i)
    {
        AA = (A1 + A3 + 2)&MOD;
        BB = (B1 + A2)&MOD;
        A3 = A2;
        A2 = A1;
        A1 = AA;
        B2 = B1;
        B1 = BB;
        ///A[i] = (A[i-1] + A[i-3] + 2)&MOD;
        ///B[i] = (B[i-1] + A[i-2])&MOD;
    }
    printf("%d\n",(A1+B1)&MOD);
    return 0;
}