#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

struct matrix
{
    long long m[2][2];
    void operator *= (const matrix &a)
    {
        int i, j, k;
        matrix c;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
            {
                c.m[i][j] = 0; //initializarea;
                for(int k = 0; k < 2; k++)
                    c.m[i][j] += m[i][k] * a.m[k][j];
                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];
    }
};

matrix lg_put(matrix b, matrix rez, int exp)//ridicare la putere in timp logaritmic cu op pe biti
{
    for(int bit = 1; bit <= exp; bit <<= 1)
    {
        if(exp & bit)
            rez *= b; // rez = 1ll *
        b *= b; // b = 1ll * b * b % MOD
    }
    return rez;
}

matrix b = {0,1,1,1}, rez = {1,1,0,0,};

int main()
{
    int k;
    fin >> k;

    rez = lg_put(b,rez,k-1);
    fout<< rez.m[0][0];
    /*for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                cout << rez.m[i][j];*/
    return 0;
}