#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
typedef long long ll;
const ll MOD=666013;
struct matrix{
    vector<vector<ll>> data;
    ll l,w;
    matrix(ll n=0,ll m=0){
        l=n,w=m;
        data.resize(n);
        for(auto& it : data)
            it.resize(m);
    }
    matrix(vector<vector<ll>> b){
        data=b,l=b.size(),w=b.size()?(*b.begin()).size():0;
    }
    matrix operator * (matrix b){
        matrix ans(l,b.w);
        for(int i=0;i<l;i++){ /// w=b.l;
            for(int j=0;j<b.w;j++){
                for(int k=0;k<w;k++)
                    ans.data[i][j]+=data[i][k]*b.data[k][j],ans.data[i][j]%=MOD;
            }
        }
        return ans;
    }
};
vector<vector<ll>> fib_step={{1,1},{1,0}},fib_init={{0,1}};
matrix pw(matrix a, ll n){
    matrix ans(fib_step);
    for(;n;n>>=1,a=a*a)
        if(n&1)
            ans=ans*a;
    return ans;
}
int main()
{
    matrix a(fib_step);
    ll n;
    fin>>n;
    if(n<2)
        fout<<n;
    else
        fout<<pw(a,n-2).data[0][0];
    return 0;
}