#include<fstream>
#include<algorithm>
using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const int mod=666013;
int n,z[2][2]={{0,1},{1,1}},fib[2][2]={{1,0},{1,0}};
void inmultire(int a[2][2],int b[2][2]){
    int rez[2][2]={0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            for(int k=0;k<2;k++)
                rez[i][j]=(rez[i][j]+(1LL*a[i][k]*b[k][j])%mod)%mod;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            a[i][j]=rez[i][j];
}
void Ridic(int n){
    while(n){
        if(n%2==1) inmultire(fib,z);
        inmultire(z,z);
        n/=2;
    }
}
int main(){
    cin>>n;
    Ridic(n);
    cout<<fib[1][1];
}