#include <cassert>
#include<cstdio>
#define M 1048576
#define N 5
using namespace std;

class mat{
public:
    int A[N][N];

    mat(){
        int i,j;
        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                A[i][j]=0;
    }

    void fill(){
        A[0][0]=A[0][1]=A[1][2]=A[1][3]=A[2][0]=A[3][3]=A[4][4]=1;
        A[4][0]=2;
    }

    mat operator *(mat B){
        mat C;
        int i,j,l;

        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                for(l=0;l<N;l++){
                    C.A[i][j]+=((1LL*B.A[i][l]*A[l][j])%M)-M;
                    if (C.A[i][j]<0) C.A[i][j]+=M;
                }

        return C;
    }
};

mat pow(mat A,int n){
    if (n==1) return A;

    if (n&1) return A*pow(A,n-1);
    return pow(A*A,n/2);
}

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

    A.fill();
    scanf ("%d",&n);

    if (n==1){
        printf ("1");
        return 0;
    }

    A=pow(A,n-1);
    int v[N];

    for(i=0;i<N;i++){
        v[i]=A.A[i][0]+A.A[i][3]-M;
        if (v[i]<0) v[i]+=M;
    }

    int ans=(v[4]+2*v[0]-2*v[2])%M;
    if (ans<0) ans+=M;

    int ans2 = (1LL * n * n - n) % M;
    assert(ans == ans2);

    printf ("%d",ans);
    return 0;
}