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

const int MOD = 666013;

void inmultire(int a[2][2], int b[2][2], int rez[2][2])
{
    // brute
    // rez[0][0] = a[0][0]*b[0][0] + a[0][1]*b[1][0];

    // sau:
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++) {
            int s = 0;

            for (int k = 0; k < 2; k++)
                s = (s + (long long)a[i][k]*b[k][j] % MOD) % MOD;

            rez[i][j] = s;
        }
}

void putere(int a[2][2], int k, int rez[2][2])
{
    if (k == 0) {
        rez[0][0] = 1;
        rez[0][1] = 0;
        rez[1][0] = 0;
        rez[1][1] = 1;
    }
    else {
        int x[2][2];
        putere(a, k/2, x);

        if (k % 2 == 0) {
            inmultire(x,x,rez);
        }
        else {
            int y[2][2];
            inmultire(x,x,y);
            inmultire(a,y,rez);
        }
    }
}


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

    int k;
    fin >> k;

    int a[2][2];
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;

    if (k == 0)
        fout << 0 << endl;
    else {
        int rez[2][2];
        putere(a, k, rez);
        fout << rez[1][0] << endl;
    }

    return 0;
}