#include <iostream>
#include <fstream>
using namespace std;
const long long MODULO=666013;
void matrix_szorzas(int eredmeny[][2], int a[][2], int b[][2]);
void matrix_masolas(int cel[][2], int forras[][2]);
void matrix_hatv(int a[][2], int n)
{
    if (n==0)
    {
        a[0][0] = 1;
        a[0][1] = 0;
        a[1][0] = 0;
        a[1][1] = 1;
    }
    else if (n > 1)
    {
        if (n % 2 ==0)
        {
            int eredmeny[2][2];
            matrix_szorzas(eredmeny,a,a);
            matrix_hatv(eredmeny,n/2);
            matrix_masolas(a,eredmeny);
        }
        else
        {
            int eredmeny[2][2];
            int szorzat[2][2];
            matrix_szorzas(eredmeny,a,a);
            matrix_hatv(eredmeny,n/2);
            matrix_szorzas(szorzat,eredmeny,a);
            matrix_masolas(a,szorzat);

        }
    }
}
void matrix_szorzas(int eredmeny[][2], int a[][2], int b[][2])
{
    eredmeny[0][0] = (((long long)a[0][0])*b[0][0]+((long long)a[0][1])*b[1][0])%MODULO;
    eredmeny[0][1] = (((long long)a[0][0])*b[0][1]+((long long)a[0][1])*b[1][1])%MODULO;
    eredmeny[1][0] = (((long long)a[1][0])*b[0][0]+((long long)a[1][1])*b[1][0])%MODULO;
    eredmeny[1][1] = (((long long)a[1][0])*b[0][1]+((long long)a[1][1])*b[1][1])%MODULO;
}
void matrix_masolas(int cel[][2], int forras[][2])
{
    for ( int i = 0; i <= 1; i++)
        for ( int j = 0; j <= 1; j++)
        {
            cel[i][j]=forras[i][j];
        }
}
int main()
{
    int a[2][2],n;
    a[0][0] = 0;
    a[0][1] = 1;
    a[1][0] = 1;
    a[1][1] = 1;
    ifstream be("kfib.in");
    be >> n;
    matrix_hatv(a,n-1);
    ofstream ki("kfib.out");
    ki<<(a[0][0]+a[1][0])%MODULO;
    return 0;
}