#include <iostream>
#include <fstream>

using namespace std;

ifstream input("kfib.in");
ofstream output("kfib.out");

const int MOD = 666013;

void multiplyMatrix(int m1[2][2], int m2[2][2])
{
    int temp[2][2];
    temp[0][0] = (m2[0][0]*m1[0][0] + m2[1][0]*m1[0][1])%MOD;
    temp[1][0] = (m2[0][0]*m1[1][0] + m2[1][0]*m1[1][1])%MOD;
    temp[0][1] = (m2[0][1]*m1[0][0] + m2[1][1]*m1[0][1])%MOD;
    temp[1][1] = (m2[0][1]*m1[1][0] + m2[1][1]*m1[1][1])%MOD;

    m1[0][0] = temp[0][0];
    m1[1][0] = temp[1][0];
    m1[0][1] = temp[0][1];
    m1[1][1] = temp[1][1];
}

void fastExponent(int m[2][2], int k)
{
    if(k == 1){
        return;
    }
    if(k % 2 == 0){
        fastExponent(m, k/2);
        multiplyMatrix(m, m);
    }
    else{
        int temp[2][2];
        temp[0][0] = m[0][0];
        temp[0][1] = m[0][1];
        temp[1][0] = m[1][0];
        temp[1][1] = m[1][1];
        multiplyMatrix(m, m);
        fastExponent(m, k/2);
        multiplyMatrix(m, temp);
    }

}

int main()
{
    int m1[2][2] = {{0, 1}, {0, 0}};
    int m2[2][2] = {{1, 1}, {1, 0}};
    int k;
    input >> k;

    fastExponent(m2, k);

    multiplyMatrix(m1, m2);

    output << m1[0][0];
    return 0;
}