#include <fstream>

using namespace std;

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

const int p = 666013;

void Putere(int &a, int &b, int &c, int &d, int k)
{
    int a1, b1, c1, d1;
    int a2, b2, c2, d2;
    a1 = a;
    b1 = b;
    c1 = c;
    d1 = d;
    if (k > 1)
        if (k % 2 == 1)
            {
             Putere(a, b, c, d, k-1);
             a2 = a;
             b2 = b;
             c2 = c;
             d2 = d;
             a = ((1LL * a1 * a2) % p + (1LL * b1 * c2) % p) % p;
             b = ((1LL * a1 * b2) % p + (1LL * b1 * d2) % p) % p;
             c = ((1LL * c1 * a2) % p + (1LL * d1 * c2) % p) % p;
             d = ((1LL * c1 * b2) % p + (1LL * d1 * d2) % p) % p;
            }
        else
            {
             a = ((1LL * a1 * a1) % p + (1LL * b1 * c1) % p) % p;
             b = ((1LL * a1 * b1) % p + (1LL * b1 * d1) % p) % p;
             c = ((1LL * c1 * a1) % p + (1LL * d1 * c1) % p) % p;
             d = ((1LL * c1 * b1) % p + (1LL * d1 * d1) % p) % p;
             Putere(a, b, c, d, k/2);
            }
}

int main()
{
    int k, a, b, c, d;
    fin >> k;
    fin.close();
    a = 0;
    b = c = d = 1;
    Putere(a, b, c, d, k-1);
    fout << (d % p) << "\n";
    fout.close();
    return 0;
}