#include <fstream>
#include <string.h>
#define RST 666013

using namespace std;

int c[3][3] = {{0, 0, 0}, {0, 0, 1}, {0, 1, 1}}, sol[3][3];

void mul(int a[3][3], int b[3][3], int rez[3][3])
{
    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            for(int k = 1; k <= 2; k++)
                rez[i][j] = (rez[i][j] + 1LL * a[i][k] * b[k][j]) % RST;
}

void lgput(int m[3][3], int put)
{
    int aux[3][3]; m[1][1] = m[2][2] = 1;
    while(put)
    {
        if(put & 1)
        {
            memset(aux, 0, sizeof(aux));
            mul(m, c, aux);
            memcpy(m, aux, sizeof(aux));
        }
        memset(aux, 0, sizeof(aux));
        mul(c, c, aux);
        memcpy(c, aux, sizeof(aux));
        put >>= 1;
    }
}

int main()
{
    ifstream in("kfib.in"); ofstream out("kfib.out");
    int n; in>>n; in.close();
    lgput(sol, n - 1);
    out<<sol[2][2]<<'\n'; out.close();
    return 0;
}