#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");

int n, p, i, j;
int f[3][3], constanta[3][3];


void InmultireMatrice(int f[3][3], int m[3][3]){
    int a=(f[1][1]*m[1][1]+f[1][2]*m[2][1])%666013;
    int b=(f[1][1]*m[1][2]+f[1][2]*m[2][2])%666013;
    int c=(f[2][1]*m[1][1]+f[2][2]*m[2][1])%666013;
    int d=(f[2][1]*m[1][2]+f[2][2]*m[2][2])%666013;
    f[1][1]=a;
    f[1][2]=b;
    f[2][1]=c;
    f[2][2]=d;
}



void putere(int f[3][3], int p){
    if(p==0 || p==1){
        return;
    }
    putere(f, p/2);
    InmultireMatrice(f, f);
    if(p%2==1){
        InmultireMatrice(f, constanta);
    }
}


int main(){
    fin>>p;
    constanta[1][1]=0;
    constanta[1][2]=1;
    constanta[2][1]=1;
    constanta[2][2]=1;
    f[1][1]=1;
    f[1][2]=1;
    f[2][1]=1;
    f[2][2]=0;
    putere(f, p-1);
    fout<<f[1][1]%666013;

}