#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
#define ll unsigned long long
#define maxi 666013
int main()
{
    ll n,x=1,y=1,z=0;
    fin>>n;
    if(n==0){
        fout<<0;
        return 0;
    }else if(n==1 or n==2){
        fout<<1;
        return 0;
    }
    for(int i=3;i<=n;++i){
        z=(x+y)%maxi;
        x=y;
        y=z;
    }
    fout<<z;
    return 0;
}