#include<cstdio>
using namespace std;

const int mod=(1<<20)-1;

int n;
int a1,a2,a3,a4;
int b1,b2;

int main() {
    freopen("12perm.in","r",stdin);
    freopen("12perm.out","w",stdout);
    scanf("%d",&n);
    a1=2;
    a2=4;
    a3=8;
    b1=4;
    
    if(n==1) {
        printf("1");
    }
    else if(n==2) {
        printf("2");
    }
    else if(n==3) {
        printf("6");
    }
    else if(n==4) {
        printf("12");
    }

    for(int i=5;i<=n;i++) {
        a4=(a3+a1+2)&mod;
        b2=(b1+a2)&mod;
        a1=a2;a2=a3;a3=a4;
        b1=b2;
    }
    printf("%d",a4+b2);
}