#include <bits/stdc++.h>
#define int long long

using namespace std;

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

const int mod=666013;

int n;
vector <vector<int>> v;

vector <vector<int>> prod (vector <vector<int>> a, vector <vector<int>> b)
{
    vector <vector<int>> rez;
    rez.resize(a.size());
    for (int i=0; i<rez.size(); i++)
        rez[i].resize(b[0].size());
    for (int i=0; i<a.size(); i++)
    {
        for (int j=0; j<b[0].size(); j++)
        {
            for (int k=0; k<a[0].size(); k++)
            {
                rez[i][j]=(rez[i][j]+a[i][k]*b[k][j])%mod;
            }
        }
    }
    return rez;
}

vector <vector<int>> lgput (vector <vector<int>> a, int b)
{
    vector <vector<int>> p;
    p={{1,0},{0,1}};
    while (b)
    {
        if (b%2==1)
            p=prod(p,a);
        a=prod(a,a);
        b/=2;
    }
    return p;
}

signed main()
{
    fin >> n;
    v={{0,1},{1,1}};
    v=lgput(v,n);
    v=prod(v,{{0},{1}});
    fout << v[0][0];
    return 0;
}