#include <iostream>
#include <fstream>
#define mod 666013

using namespace std;

void Inmultire(long long X[2][2], long long Y[2][2])
{
    long long a, b, c, d;

    a = ((X[0][0] % mod * Y[0][0] % mod) % mod + (X[0][1] % mod * Y[1][0] % mod) % mod) % mod;
    b = ((X[0][0] % mod * Y[0][1] % mod) % mod + (X[0][1] % mod * Y[1][1] % mod) % mod) % mod;
    c = ((X[1][0] % mod * Y[0][0] % mod) % mod + (X[1][1] % mod * Y[1][0] % mod) % mod) % mod;
    d = ((X[1][0] % mod * Y[0][1] % mod) % mod + (X[1][1] % mod * Y[1][1] % mod) % mod) % mod;

    Y[0][0] = a;
    Y[0][1] = b;
    Y[1][0] = c;
    Y[1][1] = d;
}

/**

00 01   00 01
10 11   10 11

*/

void Afisare(int a[][2])
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
}

void RidicareLaPutere(int n, long long a[][2])
{
    long long I[2][2] = {{1, 0}, {0, 1}};

    while(n)
    {
        if(n % 2 == 1)
            Inmultire(a, I);
        Inmultire(a, a);
        n = n / 2;
    }
    a[0][0] = I[0][0];
    a[0][1] = I[0][1];
    a[1][0] = I[1][0];
    a[1][1] = I[1][1];
}

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

    int k;
    long long a[2][2] = {{0, 1}, {1, 1}};

    f >> k;

    if(k == 0)
        g << 0;
    else
    {
        RidicareLaPutere(k - 1, a);
        g << a[1][1];
    }

    return 0;
}