#include <bits/stdc++.h>

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

const int MOD = 666013;

struct Mat1
{
    long long x11;
    long long x21;
};

struct Mat2
{
    long long x11 , x12;
    long long x21 , x22;
};

Mat2 Inm(Mat2 a , Mat2 b)
{
    Mat2 rasp;
    rasp.x11 = ((a.x11 * b.x11) % MOD + (a.x12 * b.x21) % MOD) % MOD;
    rasp.x12 = ((a.x11 * b.x12) % MOD + (a.x12 * b.x22) % MOD) % MOD;
    rasp.x21 = ((a.x21 * b.x11) % MOD + (a.x22 * b.x21) % MOD) % MOD;
    rasp.x22 = ((a.x21 * b.x12) % MOD + (a.x22 * b.x22) % MOD) % MOD;
    return rasp;
}

Mat1 Inm (Mat2 a , Mat1 b)
{
    Mat1 rasp;
    rasp.x11 = ((a.x11 * b.x11) % MOD + (a.x12 * b.x21) % MOD) % MOD;
    rasp.x21 = ((a.x21 * b.x11) % MOD + (a.x22 * b.x21) % MOD) % MOD;
    return rasp;
}

Mat2 Power(Mat2 m , int e)
{
    Mat2 rasp = m;
    e--;
    while(e)
        {
            if(e % 2)
                rasp = Inm(rasp , m) , e--;
            else
                {
                    m = Inm(m , m);
                    e /= 2;
                }
        }
    return rasp;
}

int main()
{
    int n;
    fin >> n;
    if(n <= 2)
        cout << 1;
    else
        {
            Mat2 a = {1 , 1 , 1 , 0} ; Mat1 b = {1 , 1};
            Mat2 A = Power(a , n - 2);
            Mat1 R = Inm(A , b);
            fout << R.x11;
        }
}