#include <fstream>
#include <iostream>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long int f[3],s[3];
struct matrice
{
    long long int a;
    long long int b;
    long long int c;
    long long int d;
    matrice(long long int a=0, long long int b=0, long long int c=0, long long int d=0): a(a), b(b),c(c),d(d){}

    matrice operator*(const matrice& x) const
    {
        return matrice(((x.a*a)%MOD + (x.b*c)%MOD)%MOD, ((x.a*b)%MOD + (x.b*d)%MOD)%MOD, ((x.c*a)%MOD + (x.d*c)%MOD)%MOD, ((x.c*b)%MOD+(x.d*d)%MOD)%MOD);
    }
}mat,sol;

matrice exp(matrice mat,int e);

int main()
{
    mat.a = 0;
    mat.b = mat.c = mat.d = 1;

    int K;
    fin>>K;

    sol = exp(mat,K-1);

    f[1] = f[2] = 1;
    s[1] = (f[1]*sol.a%MOD+f[2]*sol.c%MOD)%MOD;

    fout<<s[1]<<'\n';
    return 0;
}

matrice exp(matrice mat,int e)
{
    if(e == 1)
        return mat;
    else if(e%2 == 0)
    {
        sol = exp(mat,e/2);
        return sol*sol;
    }
    else
    {
        sol = exp(mat,e/2);
        return sol*sol*mat;
    }
}