#include <bits/stdc++.h>

using namespace std;

#define MOD 666013
typedef vector<long long> vect;

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

vect multiply(vect x, vect y)
{
    vect mat(4);
    mat[0] = (x[0]*y[0]+x[1]*y[2])%MOD;
    mat[1] = (x[0]*y[1]+x[1]*y[3])%MOD;
    mat[2] = (x[2]*y[0]+x[3]*y[2])%MOD;
    mat[3] = (x[2]*y[1]+x[3]*y[3])%MOD;
    return mat;
}

int main()
{
    vect init = {1,0,0,1}, fib = {0,1,1,1};
    int n;
    fin>>n;
    n--;
    while(n > 0)
    {
        if(n%2)
            init = multiply(fib, init), n--;
        else
            fib = multiply(fib, fib), n /= 2;
    }
    fout<<init[3];
    return 0;
}