#include <bits/stdc++.h>
#define int long long int
const int mod = 666013;
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
struct Matrice {
    int a[3][3];
};
void produs(Matrice A, Matrice B,Matrice &rez)
{
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            rez.a[i][j] = 0;
    for(int i = 0 ; i < 2; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                rez.a[i][j] = (rez.a[i][j] + A.a[i][k] * B.a[k][j] + mod) % mod;

}
void exp(Matrice &M, int power)
{
    Matrice rez;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            rez.a[i][j] = 0;
    rez.a[0][0] = 1;
    rez.a[1][1] = 1;
    Matrice copym;
    for(int i = 0; i <= 2; i++)
        for(int j = 0; j <= 2; j++)
            copym.a[i][j] = M.a[i][j];
    while(power)
    {
        if(power % 2 == 1)
            produs(rez, M, rez);
        produs(M, M, M);
        power /= 2;
    }
    M = rez;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    fin >> k;
    Matrice M;
    M.a[0][0] = 1;
    M.a[1][1] = 0;
    M.a[1][0] = 1;
    M.a[0][1] = 1;
    exp(M, k - 1);
    fout << M.a[0][0] << '\n';
    return 0;
}