#include <fstream>
#include <iostream>
#define r 666013
using namespace std;

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

void produs(int p[2][2], int a[2][2], int b[2][2])
{
    int aux[2][2];
    aux[0][0] = (a[0][0]*b[0][0]%r + a[0][1]*b[1][0]%r)%r;
    aux[0][1] = (a[0][0]*b[0][1]%r + a[0][1]*b[1][1]%r)%r;
    aux[1][0] = (a[1][0]*b[0][0]%r + a[1][1]*b[1][0]%r)%r;
    aux[1][1] = (a[1][0]*b[0][1]%r + a[1][1]*b[1][1]%r)%r;

    p[0][0] = aux[0][0], p[0][1] = aux[0][1];  ///de ce mai e nevoie de un auxiliar?
    p[1][0] = aux[1][0], p[1][1] = aux[1][1];
}

void putere(int p[2][2], int a[2][2], int n) ///calculeaza (matricea a)^n
{
    if (n==0)
    {
        p[0][0] = p[1][1]= 1; //matricea unitate I2
        p[0][1] = p[1][0]= 0;
        return;
    }
    if (n%2 == 0)
    {
        produs (a, a, a);
        putere (p, a, n/2);
    }
    else
    {
        int aux[2][2];
        aux[0][0] = a[0][0], aux[0][1] = a[0][1];
        aux[1][0] = a[1][0], aux[1][1] = a[1][1];
        produs (a, a, a);
        putere (p, a, n/2);
        produs (p, p, aux);
    }
}

int main()
{
    int F[2][2], k, p[2][2];
    F[0][0] = 1, F[0][1] = 1;
    F[1][0] = 1, F[1][1] = 0;
    p[0][0] = p[1][1] = 1;
    p[0][1] = p[1][0] = 0;
    f >> k;
    if (k==0)
    {
        g << "0";
        return 0;
    }
    if (k==1||k==2)
    {
        g << "1";
        return 0;
    }
    putere(p, F, k-1);
    g << p[0][0]; //al k-lea termen Fibonacci
    return 0;
}