#include<fstream>
#include<cstring>
#define dim 666013
using namespace std;
long long n, i, ri[4][4], a[4][4], c[4][4];
ifstream in("kfib.in");
ofstream out("kfib.out");
void inmulteste(long long c[4][4], long long ri[4][4], long long a[4][4]){
    for(int i=1; i<=3; i++){
        for(int j=1; j<=3; j++){
            c[i][j]=0;
            for(int k=1; k<=3; k++){
                c[i][j]+=((ri[i][k]%dim)*(a[k][j]%dim))%dim;
                c[i][j]%=dim;
            }
        }
    }
}
int main(){
    in>>n;
    if(n==0 || n==1 || n==2 || n==3){
        if(n==0)
            out<<"0";
        if(n==1 || n==2)
            out<<"1";
        if(n==3)
            out<<"2";
    }
    else{
        for(i=1; i<=3; i++)
            ri[i][i]=1;
        a[1][2]=1;
        a[2][3]=1;
        a[3][2]=1;
        a[3][3]=1;
        n-=3;
        while(n!=0){
            if(n%2==1){
                inmulteste(c, ri, a);
                memcpy(ri, c, sizeof(ri));
            }
            inmulteste(c, a, a);
            memcpy(a, c, sizeof(a));
            n/=2;
        }
        out<<((ri[3][2]%dim)+(ri[3][3]*2)%dim)%dim;
    }
return 0;
}