#include <iostream>
#include <fstream>
using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
const int mod = 666013;
int rez[3][3];
int init[3][3];
int aux[3][3];

void inmult(int m1[3][3], int m2[3][3])
{
    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            aux[i][j] = 0;
    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            for(int k = 1; k <= 2; k++)
                aux[i][j] = (aux[i][j] + 1LL * m1[i][k] * m2[k][j]) % mod;
}

int main()
{
    int k;
    in >> k;
    k--;
    init[1][1] = 0;
    init[1][2] = 1;
    init[2][1] = 1;
    init[2][2] = 1;
    rez[1][1] = 1;
    rez[1][2] = 1;
    while(k)
    {
        if(k % 2 == 1)
        {
            inmult(rez, init);
            for(int i = 1; i <= 2; i++)
                for(int j = 1; j <= 2; j++)
                    rez[i][j] = aux[i][j];
        }
        inmult(init, init);
        for(int i = 1; i <= 2; i++)
            for(int j = 1; j <= 2; j++)
                init[i][j] = aux[i][j];
        k = k / 2;
    }
    out << rez[1][1] << "\n";
    return 0;
}