#include <bits/stdc++.h>
#define NMAX (int)(1e5+4)
#define MOD 666013
#define ft first
#define sd second
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
typedef pair <int, int> pairINT;
struct matrix{
    long long m[2][2];
    matrix operator*(const matrix& other) const{
        matrix t;
        for(int i=0;i<2;++i)
            for(int j=0;j<2;++j){
                for(int q=0;q<2;++q)
                    t.m[i][j]=(t.m[i][j] + (m[i][q] * other.m[q][j])%MOD)%MOD;
            }
        return t;
    }
    void I2(){
        m[0][1]=m[1][0]=0;
        m[0][0]=m[1][1]=1;
    }
    matrix(){
        memset(m, 0, sizeof m);
    }
};
 
int k;
 
matrix explog(matrix,int);
 
int main(){
    int f0=0, f1=1;
    fin>>k;
    if(k<=1){
        fout<<k;
        return 0;
    }
    matrix T;
    T.m[0][1]=T.m[1][0]=T.m[1][1]=1;
 
    T=explog(T, k-1);
    fout<<((f0*T.m[0][1])%MOD + (f1*T.m[1][1])%MOD)%MOD;
    return 0;
}
matrix explog(matrix A,int n){//A^n
    matrix sol;
    sol.I2();
    while(n){
        if(n%2){
            sol=sol*A;
        }
        A=A*A;
        n/=2;
    }
    return sol;
}