#pragma GCC optimize("O1")
#include <bits/stdc++.h>
#define int long long

using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");

vector <vector <int>> a;
int MOD = 666013;

vector <vector <int>> Multiply(vector <vector <int>> a,vector <vector <int>> b){
    vector <vector <int>> c;
    c.resize(2);
    c[0].resize(2);
    c[1].resize(2);
    c[0][0] = (a[0][0]*b[0][0]+a[0][1]*b[1][0])%MOD;
    c[0][1] = (a[0][0]*b[0][1]+a[0][1]*b[1][1])%MOD;
    c[1][0] = (a[1][0]*b[0][0]+a[1][1]*b[1][0])%MOD;
    c[1][1] = (a[1][0]*b[0][1]+a[1][1]*b[1][1])%MOD;
    return c;
}

vector <vector <int>> Exponentiere_Rapida(vector <vector <int>> a,int k){
    vector <vector <int>> ans;
    ans.resize(2);
    ans[0].resize(2);
    ans[1].resize(2);
    ans[0][0] = 1;
    ans[0][1] = 0;
    ans[1][0] = 0;
    ans[1][1] = 1;
    while (k){
        if (k%2==1){
            ans = Multiply(a,ans);
        }
        a = Multiply(a,a);
        k /= 2;
    }
    return ans;
}

signed main()
{
    int k;
    fin >> k;
    a.resize(2);
    a[0].resize(2);
    a[1].resize(2);
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    a = Exponentiere_Rapida(a,k);
    fout << a[1][0];
    return 0;
}