#include <bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

void inm(int mat[2][2], int mat2[2][2]){
    int rez[2][2] = {0};
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                rez[i][j] = (rez[i][j] + 1LL*mat[i][k]*mat2[k][j])%MOD;
            }
        }
    }

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            mat2[i][j] = rez[i][j];
}

void pow(int mat[2][2], int e){
    int rez[2][2]={{1,0},{0,1}};
    while(e){
        if(e%2){
            inm(mat, rez);
        }
        inm(mat, mat);
        e /= 2;
    }

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            mat[i][j] = rez[i][j];
}

int n;
int mat[2][2]={{1,1},{1,0}}, fib[2][2]={{1,0},{0,0}};
int main()
{
    fin>>n;
    if(n==0){
        fout<<0;
        return 0;
    }
    pow(mat, n-1);
    inm(mat, fib);
    fout<<fib[0][0];
    return 0;
}