#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=666013;
int n;
int a[5],mat[5][5];
void mult(int a[5][5], int b[5][5]){
    int sol[5][5];
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            sol[i][j]=0;
        }
    }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                sol[i][j]+=a[i][k]*b[k][j]%mod;
                sol[i][j]%=mod;
            }
        }
    }
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            a[i][j]=sol[i][j];
        }
    }
}
void rid_put(int a[5][5], int e){
    int c[5][5];
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            c[i][j]=a[i][j];
            if(i==j){
                a[i][j]=1;
            }
            else{
                a[i][j]=0;
            }
        }
    }
    while(e){
        if(e%2){
            mult(a,c);
        }
        mult(c,c);
        e/=2;
    }
}
signed main(){
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    f>>n;
    a[1]=a[2]=1;
    mat[1][1]=mat[1][2]=mat[2][1]=1;
    if(n<=2){
        g<<1;
        return 0;
    }
    else{
        rid_put(mat,n-2);
        int sol[5];
        for(int i=1;i<=2;i++){
            sol[i]=0;
        }
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++){
                sol[i]+=mat[i][j]*a[j]%mod;
                sol[i]%=mod;
            }
        }
        g<<sol[1];
    }
    return 0;
}