#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
long long  k,m[3][3],rez[3][3],m1[3][3],rez1[3][3];
int main(){
    int i, j;
    cin>>k;
    k=k-2;
    m[1][2]=m[2][1]=m[2][2]=1;
    rez[1][1]=rez[2][2]=1;
    while(k!=0){
        if(k%2==1){
            k--;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    rez1[i][j]=rez[i][j]; //copie;
            rez[1][1]=((rez1[1][1]*m[1][1])%mod+(rez1[1][2]*m[2][1])%mod)%mod;
            rez[1][2]=((rez1[1][1]*m[1][2])%mod+(rez1[1][2]*m[2][2])%mod)%mod;
            rez[2][1]=((rez1[2][1]*m[1][1])%mod+(rez1[2][2]*m[2][1])%mod)%mod;
            rez[2][2]=((rez1[2][1]*m[1][2])%mod+(rez1[2][2]*m[2][2])%mod)%mod;
        }
        else{
            k=k/2;
            for(i=1;i<=2;i++)
                for(j=1;j<=2;j++)
                    m1[i][j]=m[i][j]; //copie
            m[1][1]=((m1[1][1]*m1[1][1])%mod+(m1[1][2]*m1[2][1])%mod)%mod;
            m[1][2]=((m1[1][1]*m1[1][2])%mod+(m1[1][2]*m1[2][2])%mod)%mod;
            m[2][1]=((m1[2][1]*m1[1][1])%mod+(m1[2][2]*m1[2][1])%mod)%mod;
            m[2][2]=((m1[2][1]*m1[1][2])%mod+(m1[2][2]*m1[2][2])%mod)%mod;
        }
    }
    cout<<(rez[1][2]+rez[2][2])%mod;
    return 0;
}