#include <iostream>
#include <cstring>
#define mod 666013

void prod(long long int A[][2],long long int B[][2],long long int R[][2]){
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                R[i][j] += (A[i][k] * B[k][j]) % mod;
            }
        }
    }
}

void fibonace(int p,long long int sol[][2]){
    long long int mat[2][2];
    mat[0][0] = 0;
    mat[0][1] = 1;
    mat[1][0] = 1;
    mat[1][1] = 1;
    long long int Temp[2][2];
    while(p != 0){
        if(p % 2 == 1){
            memset(Temp,0,sizeof(Temp));
            prod(sol,mat,Temp);
            memcpy(sol,Temp,sizeof(Temp));
        }
        memset(Temp,0,sizeof(Temp));
        prod(mat,mat,Temp);
        memcpy(mat,Temp,sizeof(mat));
        p/=2;
    }
}

int main()
{
    long long int sol[2][2];

    sol[0][0] = 1;
    sol[0][1] = 0;
    sol[1][0] = 0;
    sol[1][1] = 1;
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int p;

    scanf("%d",&p);
    fibonace(p-1,sol);
    printf("%lld",sol[1][1]);
    return 0;
}