#include <iostream>
#include <fstream>
using namespace std;
long long mat[3][3];
long long c[3][3],sol[3][3],ans[3][3],rasp[3][3];
void inm1(){
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            int sum=0;
            for(int k=1;k<=2;k++){
                sum+=(ans[i][k]*mat[k][j])%666013;
                sum%=666013;
            }
            rasp[i][j]=sum;
        }
    }
    ans[1][1]=rasp[1][1];
    ans[1][2]=rasp[1][2];
    ans[2][1]=rasp[2][1];
    ans[2][2]=rasp[2][2];
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            rasp[i][j]=0;
        }
    }
}
void inm2(){
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            int sum=0;
            for(int k=1;k<=2;k++){
                sum+=(mat[i][k]*mat[k][j])%666013;
                sum%=666013;
            }
            rasp[i][j]=sum;
        }
    }
    mat[1][1]=rasp[1][1];
    mat[1][2]=rasp[1][2];
    mat[2][1]=rasp[2][1];
    mat[2][2]=rasp[2][2];
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            rasp[i][j]=0;
        }
    }
}
void lgput(long long e){
    while(e){
        if(e%2==1){
            inm1();
        }
        inm2();
        e/=2;
    }
}
int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    long long n;
    mat[1][1]=0;
    mat[1][2]=1;
    mat[2][1]=1;
    mat[2][2]=1;
    ans[1][1]=mat[1][1];
    ans[1][2]=mat[1][2];
    ans[2][1]=mat[2][1];
    ans[2][2]=mat[2][2];
    cin>>n;
    lgput(n);
    cout<<ans[1][1];
    return 0;
}