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

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

class matrice
{
public:
    long long a, b, c, d;
    matrice patrat()
    {
        matrice x;
        x.a = (a * a + b * c) % MOD;
        x.b = (a * b + b * d) % MOD;
        x.c = (a * c + c * d) % MOD;
        x.d = (b * c + d * d) % MOD;
        return x;
    }
    matrice inm(matrice y)
    {
        matrice rez;
        rez.a = (a * y.a + b * y.c) % MOD;
        rez.b = (a * y.b + b * y.d) % MOD;
        rez.c = (c * y.a + d * y.c) % MOD;
        rez.d = (c * y.b + d * y.d) % MOD;
        return rez;
    }
    void print()
    {
        cout<<a<<' '<<b<<'\n'<<c<<' '<<d<<'\n'<<'\n';
    }
};

matrice pow(matrice x, int p)
{
    if (p == 1) return x;
    if (p % 2 == 0)
        return pow(x.patrat(), p / 2);
    else
        return x.inm(pow(x.patrat(), p / 2));
}
int n;
int main()
{
    f>>n;
    if (n <= 1) g << n;
    else
    {
        matrice z;
        z.a = 0;
        z.b = 1;
        z.c = 1;
        z.d = 1;
        z = pow(z, n - 1);
        g << z.d;
    }
    return 0;
}