#include <bits/stdc++.h>
using namespace std;
#define MOD 666013
struct Matrix{
    int M[2][2];
    Matrix(bool u=0){
        memset(M,0,sizeof(M));
        if(u)
            M[0][0]=M[1][1]=1;
    }
    Matrix(int a,int b,int c,int d){
        M[0][0]=a;
        M[0][1]=b;
        M[1][0]=c;
        M[1][1]=d;
    }
    Matrix &operator =(const Matrix &B){
        memcpy(M,B.M,sizeof(B.M));
        return *this;
    }
    int elem(int l,int c){
        return M[l][c];
    }
}O(0),I(1);
Matrix operator *(const Matrix &A,const Matrix &B){
    Matrix C(0);
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            for(int k=0;k<2;++k)
                C.M[i][j]=(1LL*A.M[i][k]*B.M[k][j]+C.M[i][j])%MOD;
        return C;
}
Matrix operator ^(const Matrix &A,int b){
    Matrix Ans(1),P=A;
    for(int i=1;i<=b;i<<=1){
        if(i&b)
            Ans=Ans*P;
        P=P*P;
    }
    return Ans;
}
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    int n;
    scanf("%d",&n);
    printf("%d\n",(Matrix(0,1,0,0)*((Matrix(0,1,1,1))^n)).elem(0,0));
    return 0;
}