#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

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

typedef vector<vector<int> > matrice;
const int mod = 666013;

void Resize(matrice &m, int sz)
{
    m.resize(sz);

    for(int i=0; i<m.size(); i++)
    {
        m[i].resize(sz);
    }
}

matrice inm(matrice a, matrice b)
{
    matrice c;
    Resize(c, 2);
    int i, j, k;
    for(i=0; i<a.size(); i++)
    {
        for(j=0; j<a.size(); j++)
        {
            for(k=0; k<a.size(); k++)
            {
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
            }
        }
    }
    return c;
}

matrice epq(matrice m, int p)
{
    matrice aux;
    Resize(aux, 2);
    aux[0][0] = aux[1][1] = 1;

    while(p > 1)
    {
        if(p%2)
        {
            aux = inm(aux, m);
        }
        m = inm(m, m);
        p/=2;
    }
    return inm(m, aux);
}

int main()
{
    matrice M;
    Resize(M, 2);
    M[0][0] = 0, M[0][1] = M[1][0] = M[1][1] = 1;
    int n;
    fin>>n;
    M = epq(M, n-1);
    fout<<M[1][1]%mod;
    fin.close();
    fout.close();
    return 0;
}