#include <cstdio>

using namespace std;
int mat[2][2];
int model[2][2];
const int mod = 666013;
int sol[2][2];
int mult(int a[2][2], int b[2][2])
{
    int c[2][2];
    c[0][0]=c[1][1]=c[0][1]=c[1][0]=0;
    int i,j,k;
    for(i=0; i<2; i++)
        for(j=0; j<2; j++)
            for(k=0; k<2; k++)
                c[i][j]=(c[i][j]+a[i][k]*1LL*b[k][j])%mod;
    a[0][0]=c[0][0];
    a[0][1]=c[0][1];
    a[1][0]=c[1][0];
    a[1][1]=c[1][1];
}
int lgput(int n)
{
    sol[0][0]=0;
    sol[0][1]=1;
    while(n){
        if(n%2==1)
            mult(sol, mat);
        mult(mat, mat);
        n>>=1;
    }
}
int main()
{   freopen("kfib.in", "r",stdin);
    freopen("kfib.out", "w",stdout);
    int k;
    scanf("%d", &k);
    model[0][0]=mat[0][0]=0;
    model[0][1]=mat[0][1]=1;
    model[1][0]=mat[1][0]=1;
    model[1][1]=mat[1][1]=1;
    sol[0][1]=1;
    sol[0][0]=0;
    if(k==0)
        printf("0");
    else{
        if(k==1)
            printf("1");
        else{
            lgput(k-1);
            printf("%d", sol[0][1]);
        }
    }
    return 0;
}