#include <fstream>
#include <vector>
#define m vector<vector<int>>

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

int k;

int sum(int a, int b) {return (a+b)%666013;}
int pro(int a, int b) {return (1LL*a*b)%666013;}

m prod(m a, m b)
{
    m rez;
    for(int i=0; i<a.size(); i++)
    {
        rez.push_back({});
        for(int j=0; j<b[0].size(); j++)
        {
            rez[i].push_back(0);
            for(int k=0; k<a[0].size(); k++)
                rez[i][j] = sum(rez[i][j], pro(a[i][k], b[k][j]));
        }
    }
    return rez;
}

m pow(m a, int e)
{
    if(e==0) return {{1, 0}, {0, 1}};
    m x = pow(a, e/2);
    if(e%2==0) return prod(x, x);
    else return prod(prod(x, x), a);
}

int main()
{
    fin>>k;
    m ans={{0, 1}, {1, 1}};
    m rasp = prod({{0, 1}}, pow(ans, k-1));
    fout<<rasp[0][1];
    return 0;
}