#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;
void prod(int a[3][3],int b[3][3],int c[3][3]){
    c[1][1]=(a[1][1]*b[1][1]+a[1][2]*b[2][1])%mod;
    c[1][2]=(a[1][1]*b[1][2]+a[1][2]*b[2][2])%mod;
    c[2][1]=(a[2][1]*b[1][1]+a[2][2]*b[2][1])%mod;
    c[2][2]=(a[2][1]*b[1][2]+a[2][2]*b[2][2])%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;
    initx(a);
    initx(x);
    while(n!=0){
        prod(p,p,a);
        swop(p,a);
        if(n%2==1)
            prod(p,x,a);
        swop(p,a);
        n/=2;
    }
    int S=(p[1][2]+p[2][2])%mod-(p[1][1]+p[2][1])%mod;
    if(S<0)
        S+=mod;
    g<<S;
    return 0;
}