#include <fstream>
#define mod 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
int a[3][3],p[3][3],x[3][3],n,v[1001],b;
void prod(int a[3][3],int b[3][3],int c[3][3]){
    c[1][1]=((a[1][1]*b[1][1])%mod+(a[1][2]*b[2][1])%mod)%mod;
    c[1][2]=((a[1][1]*b[1][2])%mod+(a[1][2]*b[2][2])%mod)%mod;
    c[2][1]=((a[2][1]*b[1][1])%mod+(a[2][2]*b[2][1])%mod)%mod;
    c[2][2]=((a[2][1]*b[1][2])%mod+(a[2][2]*b[2][2])%mod)%mod;
}
void swop(int a[3][3],int b[3][3]){
    for(int i=1;i<=2;i++)
        for(int j=1;j<=2;j++)
            a[i][j]=b[i][j];
}
void initx(int a[3][3]){
    a[1][1]=0;
    a[1][2]=a[2][1]=a[2][2]=1;
}
int main()
{   f>>n;
    p[1][1]=p[2][2]=1;
    n-=2;
    initx(a);
    initx(x);
    b=n;
    int k=-1;
    for(int i=1;(1<<(i-1))<=b;i++){
        v[++k]=((b>>(i-1))&1);
    }
    while(k>=0){
        prod(p,p,a);
        swop(p,a);
        if(v[k]==1)
            prod(p,x,a);
        swop(p,a);
        k--;
    }
    int S=(p[1][2]+p[2][2])%mod;
    g<<S;
    return 0;
}