#include <fstream>
#define MOD 666013

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

long long v[2][2], prod[2][2],n;

void mult (long long mat1[2][2], long long mat2[2][2])
{
    long long res[2][2];
    res[0][0]=mat1[0][0]*mat2[0][0]%MOD+mat1[0][1]*mat2[1][0]%MOD;
    res[0][0]%=MOD;
    res[0][1]=mat1[0][0]*mat2[0][1]%MOD+mat1[0][1]*mat2[1][1]%MOD;
    res[0][1]%=MOD;
    res[1][0]=mat1[1][0]*mat2[0][0]%MOD+mat1[1][1]*mat2[1][0]%MOD;
    res[1][0]%=MOD;
    res[1][1]=mat1[1][0]*mat2[0][1]%MOD+mat1[1][1]*mat2[1][1]%MOD;
    res[1][1]%=MOD;

    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            mat1[i][j]=res[i][j];
}

int main()
{
    f >> n;
    v[0][0]=0;
    v[0][1]=v[1][0]=v[1][1]=1;
    prod[0][0]=prod[1][1]=1;
    prod[0][1]=prod[1][0]=0;
    n--;
    for (int i = 1; i <= n; i <<= 1)
    {
        if(i&n) mult(prod,v);
        mult(v,v);
    }
    g << prod[1][1]%MOD << '\n';
    return 0;
}