#include <iostream>
#include <fstream>

using namespace std;

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

const int MOD = 666013;

struct MAT{
    long long m[2][2];
    void operator *= (const MAT &a){
        MAT c;
        for(int i = 0 ; i < 2 ; ++i)
            for(int j = 0 ; j < 2 ; ++j)
            {
                c.m[i][j] = 0;

                for(int k = 0 ; k < 2 ; ++k)
                    c.m[i][j] += m[k][j] * a.m[i][k];
                c.m[i][j] %= MOD;
            }
        for(int i = 0 ; i < 2 ; ++i)
            for(int j = 0 ; j <  2 ; ++j)
                m[i][j] = c.m[i][j];
    }
};

MAT x = {0,1,1,1} , rezultat = {1,0,0,1};

int main()
{
    int n;
    fin >> n;
    for(int s = 1; s <= n; s <<= 1){
        if(n & s)
            rezultat *= x;
        x *= x;
    }
    fout << rezultat.m[0][1];
    return 0;
}