#include <bits/stdc++.h>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
const int mod=666013;
struct MATRIX {
        int lin=0,col=0;
        vector<vector<int>> mat;
        MATRIX(int l,int c,int ini=0) {
                lin=l;
                col=c;
                mat.resize(lin,vector<int>(col,ini));
        }
        const MATRIX operator *(const MATRIX &other) {
                if(col==other.lin) {
                        MATRIX rez(lin,other.col);
                        for(int i=0; i<lin; i++) {
                                for(int j=0; j<other.col; j++) {
                                        for(int l=0; l<col; l++) {
                                                rez.mat[i][j]=(long long)((long long)rez.mat[i][j]+(long long)mat[i][l]*other.mat[l][j])%mod;
                                        }
                                }
                        }
                        return rez;
                }
//                else if(lin==other.col){
//                        return other*(*this);
//                } NU ESTE CORECT MATEMATIC SA FACI UNA CA ASTA
        }
};
MATRIX fib(1,2),Z(2,2);
void initMat() {
        fib.mat[0][0]=1;
        fib.mat[0][1]=0;
        Z.mat[0][0]=1;
        Z.mat[0][1]=1;
        Z.mat[1][0]=1;
        Z.mat[1][1]=0;
}
const MATRIX lgput(MATRIX X,int a) {
        MATRIX rez(X.lin,X.col,1);
        while(a) {
                if(a%2==1)
                        rez=rez*X;
                X=X*X;
                a/=2;
        }
        return rez;
}
int main() {
        int n;
        fin>>n;
        if(n==0){
                fout<<0;
                return 0;
        }
        initMat();
        fib=fib*lgput(Z,n-2);
        fout<<fib.mat[0][0];
        return 0;
}