#include <fstream>
#include<vector>
using namespace std;

#define ll long long
#define mod (ll)666013


ifstream cin("kfib.in");
ofstream cout("kfib.out");

vector<vector<ll>> prod(vector<vector<ll>> mat1,vector<vector<ll>> mat2){
    ll n1,m1,n2,m2;
    n1=mat1.size();
    m1=mat1[0].size();
    n2=mat2.size();
    m2=mat2[0].size();
    vector<vector<ll>> res=vector<vector<ll>>(n1,vector<ll>(m2));

    for(ll i=0;i<n1;i++){
        for(ll j=0;j<m2;j++){
            ll nr=0;
            for(ll y=0;y<m1;y++){
                ll nr1=mat1[i][y];
                ll nr2=mat2[y][j];
                nr+=mat1[i][y]*mat2[y][j]%mod;
                nr%=mod;
            }
            res[i][j]=nr;
        }
    }
    return res;
}

vector<vector<ll>> pow(vector<vector<ll>> mat,ll m){
    vector<vector<ll>> res=mat;
    while(m>0){
        if(m%2){
            res=prod(res,mat);
            m--;
        }
        else{
            mat=prod(mat,mat);
            m/=2;
        }
    }
    return res;
}


int main()
{
    ll k;
    vector<vector<ll>> mat1={{0,1},{1,1}};
    vector<vector<ll>> mat2={{0},{1}};

    cin>>k;
    if(k<2){
        cout<<mat2[k][0];
    }
    else{
        cout<<prod(pow(mat1,k-2),mat2)[1][0];
    }

    return 0;
}