#include <fstream>
#include <cstring>
#define MOD 666013

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

int N,a[4][4],b[4][4],r[4][4];
void Pow(int a[][4],int b[][4],int c[][4]){
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++){
            c[i][j]=0;
            for(int k=1;k<=2;k++)
                c[i][j]=(c[i][j]+1LL*a[i][k]*b[k][j])%MOD;
        }
}
void Copy(int a[][4],int b[][4]){
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            a[i][j]=b[i][j];
}
int main(){
    fin>>N;
    a[1][1]=1;
    a[1][2]=1;
    a[2][1]=1;
    a[2][2]=0;
    r[1][1]=1;
    r[1][2]=0;
    r[2][1]=0;
    r[2][2]=1;
    if(N<=2){
        fout<<1;
        return 0;
    }
    N-=2;
    while(N){
        if(N&1){
           Pow(r,a,b);
           Copy(r,b);
        }
        Pow(a,a,b);
        Copy(a,b);
        N/=2;
    }
    fout<<(r[1][1]+r[1][2])%MOD;
    return 0;
}