#include<fstream>
using namespace std;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

const int MOD = 666013;

struct mat2x2
{
    int s1,s2,j1,j2;
};


mat2x2 multiply(mat2x2 a,mat2x2 b)
{
    mat2x2 rez;
    rez.s1 = (1LL * a.s1 * b.s1 % MOD + 1LL * a.s2 * b.j1 % MOD) % MOD;
    rez.s2 = (1LL * a.s1 * b.s2 % MOD + 1LL * a.s2 * b.j2 % MOD) % MOD;
    rez.j1 = (1LL * a.j1 * b.s1 % MOD + 1LL * a.j2 * b.j1 % MOD) % MOD;
    rez.j2 = (1LL * a.j1 * b.s2 % MOD + 1LL * a.j2 * b.j2 % MOD) % MOD;

    return rez;
}

mat2x2 fastpow(mat2x2 a,int b)
{
    mat2x2 rez = {1,0,0,1};


    while(b)
        {
            if(b & 1)
                {
                    rez = multiply(rez,a);
                }

            b >>= 1;
            a = multiply(a,a);
        }

    return rez;
}

int main()
{
    int n;
    cin >> n;

    mat2x2 fibo = {1,1,1,0};

    fibo = fastpow(fibo,n - 2);

    int rez = (fibo.s1 + fibo.s2) % MOD;

    cout << rez << endl;

    return 0;// superpeace
}