#include <bits/stdc++.h>

using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int k;
int a[2][2];
int mat[2][2];
int I[2][2];
int ceva[2][2];

void Read()
{
    f>>k;
    a[0][0] = a[0][1] = 1;
    mat[0][0] = mat[1][0] = mat[0][1] = 1;
    I[0][0] = I[1][1] = 1;
}

void inmultire(int a[][2],int b[][2], int c[][2])
{
    for(int i = 0;i < 2;++i)
        for(int j = 0;j < 2;++j)
        {
            c[i][j] = 0;
            for(int k = 0;k < 2;++k)
                c[i][j] = (c[i][j] + 1LL * a[i][k] * b[k][j]) % 666013;
        }
}

int lgpower(int k)
{
    while(k)
    {
        if(k % 2 == 1)
            {
                inmultire(I, mat, ceva);
                memcpy(I, ceva, sizeof(I));
            }
        inmultire(mat, mat, ceva);
        memcpy(mat, ceva, sizeof(mat));
        k /= 2;
    }
}

int main()
{
    Read();
    lgpower(k - 1);
    inmultire(I, a, ceva);
    g<<ceva[0][0]<<'\n';
    return 0;
}