#include <bits/stdc++.h>

using namespace std;

const int MOD=666013;

#define int long long

vector<vector<int>> mul(vector<vector<int>> A, vector<vector<int>> B)
{
    vector<vector<int>> ans(A.size(), vector<int>(B[0].size(),  0));
    for(int i=0; i<ans.size(); i++)
        for(int j=0; j<ans[i].size(); j++)
            for(int k=0; k<B.size(); k++)
                ans[i][j]=(ans[i][j]+A[i][k]*B[k][j])%MOD;
    return ans;
}

vector<vector<int>> IDN(2, vector<int>(2, 0));

vector<vector<int>> matpow(vector<vector<int>> A, int exp)
{
    vector<vector<int>> rez=IDN;
    while(exp)
    {
        if(exp&1)
            rez=mul(rez, A);
        A=mul(A, A);
        exp>>=1;
    }
    return rez;
}
signed main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    IDN[0][0]=IDN[1][1]=1;
    int k;
    cin>>k;
    vector<vector<int>> T(2, vector<int>(2, 1));
    T[1][1]=0;
    T=matpow(T, k);
    vector<vector<int>> ST(2, vector<int>(1, 0));
    ST[0][0]=1;
    ST=mul(T, ST);
    cout<<ST[1][0];
    return 0;
}