#include<fstream>
#define MOD 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
long long int A[3][3],B[3][3],n;
void inmultire(long long int A[3][3],int na,long long int B[3][3],int nb){
    long long int C[3][3];
    for(int i=1;i<=na;++i){
            for(int j=1;j<=nb;++j){
                long long int s=0;
                    for(int k=1;k<=nb;++k)
                        s+=(A[i][k]*B[k][j]%MOD)%MOD;
                C[i][j]=s%MOD;
            }
        }
    for(int i=1;i<=na;++i)
        for(int j=1;j<=nb;++j)
        A[i][j]=C[i][j];
}
void putere(int n){
    --n;
    while(n){
    if(n%2)
        inmultire(A,1,B,2);
    inmultire(B,2,B,2);
    n>>=1;
    }
}
int main(){
    f>>n;
    A[1][1]=0;
    A[1][2]=1;
    B[1][1]=0;
    B[1][2]=1;
    B[2][1]=1;
    B[2][2]=1;
    putere(n);
    g<<A[1][2];
    return 0;


}