#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
ll v[2][2]={{1,1},{1,0}}, fib[2][2]={{1,0},{0,0}};
void calc(ll v[][2], ll f[][2]){
    ll sol[2][2]={0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                sol[i][j]=(sol[i][j]+v[i][k]*f[k][j])%666013;
    memcpy(f, sol, sizeof(sol));
}
void pow(ll v[][2], ll x){
    ll sol[2][2]={{1,1},{0,1}};
    while(x!=0){
        if(x%2!=0){
            calc(v,sol);
        }
        calc(v,v);
        x/=2;
    }
    memcpy(v, sol, sizeof(sol));
}
int main(){
    int n;
    fin>>n;
    if(n==0){
        fout<<0;
        return 0;
    }
    if(n==1 || n==2){
        fout<<1;
        return 0;
    }
    pow(v,n-1);
    calc(v,fib);
    fout<<fib[0][0];
}