#include <bits/stdc++.h>
using namespace std;
int dp[3][3];
int dp1[3][3];
int main()
{
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    int n,i;
    scanf("%d",&n);
    if(n==1)
    {
        printf("1\n");
        return 0;
    }
    if(n==2)
    {
        printf("2\n");
        return 0;
    }
    if(n==3)
    {
        printf("6\n");
        return 0;
    }
    dp[0][2]=1;
    dp[2][0]=1;
    dp[1][0]=1;
    dp[0][1]=1;
    dp[1][2]=dp[2][1]=1;
    int xp=2,xp1=2;
    int mod=1048576;
    for(i=4;i<=n;i++)
    {
        dp1[0][0]=dp1[1][0]=dp1[2][0]=dp1[1][1]=dp1[0][1]=dp1[2][1]=dp1[0][2]=dp1[1][2]=dp1[2][2]=0;
        dp1[0][1]=dp[0][1]+dp[0][2];
        dp1[0][2]=xp;
        dp1[1][2]=dp[0][1]+dp[2][1];
        dp1[2][1]=dp[1][0]+dp[1][2];
        dp1[1][0]=dp[1][0]+dp[2][0];
        dp1[2][0]=xp1;
        xp=dp1[0][2]+dp1[0][1];
        xp1=dp1[1][0]+dp1[2][0];
        dp[1][0]=dp1[1][0]%mod;
        dp[2][0]=dp1[2][0]%mod;
        dp[2][1]=dp1[2][1]%mod;
        dp[1][2]=dp1[1][2]%mod;
        dp[2][0]=dp1[2][0]%mod;
        dp[0][2]=dp1[0][2]%mod;
        dp[0][1]=dp1[0][1]%mod;
 }
 int mod1=dp[0][1]+dp[1][0]+dp[0][2]+dp[2][0]+dp[1][2]+dp[2][1];
 mod1%=mod;
 printf("%d",mod1);
   return 0;
}