#include<cstdio>
const int MOD=666013;
class Matrix{
    public:
        int a[3][3];
        Matrix(){
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                    a[i][j]=0;
            a[1][2]=1;
            a[2][1]=1;
            a[2][2]=1;
        }
        Matrix(int x){
            for(int i=1;i<=2;i++)
                for(int j=1;j<=2;j++)
                    a[i][j]=0;
            for(int i=1;i<=2;i++)
                a[i][i]=x;
        }
};
Matrix m;
int n;
Matrix matrix_prod(Matrix m1,Matrix m2){
    Matrix r=Matrix(0);
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            for(int k=1;k<=2;k++){
                int x=(long long)m1.a[i][k]*m2.a[k][j]%MOD;
                r.a[i][j]=(r.a[i][j]+x)%MOD;
            }
    return r;
}
Matrix matrix_pow(int a){
    if(a==0)
        return Matrix(1);
    if(a%2==0){
        Matrix nr=matrix_pow(a/2);
        return matrix_prod(nr,nr);
    }
    return matrix_prod(matrix_pow(a-1),m);
}
int main(){
    freopen("kfib.in","r",stdin);
    freopen("kfib.out","w",stdout);
    scanf("%d",&n);
    if(n<2){
        printf("%d",n);
        return 0;
    }
    Matrix res=matrix_pow(n-1);
    printf("%d",res.a[2][2]);
    return 0;
}