#include <bits/stdc++.h>

using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod = 666013;
void ridicamat(int a[2][2], int p);
void inmultiremat(int a[2][2], int b[2][2]);

int main()
{
    int n, mat[2][2];
    fin>>n;
    mat[0][0] = 0;
    mat[0][1] = mat[1][0] = mat[1][1] = 1;
    ridicamat(mat, n-2);

    fout<<(mat[0][1] + mat[1][1]) % mod;



    return 0;
}

void ridicamat(int a[2][2], int p)
{
    int rez[2][2];
    rez[0][0] = rez[1][1] = 1;
    rez[0][1] = rez[1][0] = 0;

    while(p > 0)
    {
        if(p % 2 == 1)
            inmultiremat(rez, a);
        inmultiremat(a, a);
        p /= 2;
    }

    for(int i = 0; i <= 1; ++i)
    {
        for(int j = 0; j <= 1; ++j)
            a[i][j] = rez[i][j];
    }
}

void inmultiremat(int a[2][2], int b[2][2])
{
    int aux[2][2];
    for(int i = 0; i <= 1; ++i)
        for(int j = 0; j <= 1; ++j)
            aux[i][j] = 0;

    for(int i = 0; i <= 1; ++i)
    {
        for(int j = 0; j <= 1; ++j)
        {
            for(int k = 0; k <= 1; ++k)
            {
                aux[i][j] = 1LL * (aux[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
            }
            aux[i][j] %= mod;
        }
    }

    for(int i = 0; i <= 1; ++i)
    {
        for(int j = 0; j <= 1; ++j)
            a[i][j] = aux[i][j];
    }
}