#include <iostream>
#include <fstream>
using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int MOD = 666013 ;

void multiplyMatrix(int a[][3], int b[][3]){
    int aux[3][3];
    for(int i = 1; i <= 2; i++)
    {
        for(int j = 1; j <= 2; j++)
        {
            aux[i][j] = 0;
        }
    }
    for(int i = 1; i <= 2; i++)
    {
        for(int j = 1; j <= 2; j++)
        {
            for(int k = 1; k <= 2; k++)
            {
                aux[i][j] =  aux[i][j] %  MOD + (1LL * (a[i][k] % MOD ) * (b[k][j] % MOD)) % MOD;
            }
        }
    }
    for(int i = 1; i <= 2 ;i++){
        for(int j = 1; j <= 2; j++){
            a[i][j] = aux[i][j];
        }
    }
}
void getPow(int a[][3], int p ){
    int aux[3][3];
    aux[1][1] = aux[2][2] = 1;
    aux[1][2] = aux[2][1] = 0;
    while(p){
        if(p & 1){
            multiplyMatrix(aux, a);
            --p;
        }
        multiplyMatrix(a,a);
        p = p / 2;
    }
    for(int i = 1; i <= 2; i++)
    {
        for(int j = 1; j <= 2; j++)
        {
            a[i][j] = aux[i][j];
        }
    }
}

int main(){
    int MAT[3][3];
    MAT[1][1] = 0;
    MAT[1][2] = MAT[2][1] = MAT[2][2] = 1;


    int k;
    f>>k;
    getPow(MAT,k-1);
    g<<MAT[2][2];
    return 0;
}