#include <bits/stdc++.h>

using namespace std;
ifstream in("kfib.in");
ofstream out("kfib.out");
#define MOD 666013
void mult(int a[][2],int b[][2]){
    int c[][2]={0,0,0,0};
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
        c[i][j]=(c[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]=c[i][j];
}
void pow(int a[][2],int n){
    int m[][2]={1,1,1,0};
    while(n){
        if(n%2)
            mult(m,a);
            mult(a,a);
        n/=2;
    }
  for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        a[i][j]=m[i][j];
}
int main()
{
    int n;
    in>>n;
    if(!n)
        out<<n;
    else if(n==1 && n==2)
    out<<1;
    else{
            int a[][2]={1,0,0,0};
            int m[][2]={1,1,1,0};
        pow(m,n-2);
        mult(a,m);
        out<<a[0][0];
    }
    return 0;
}