#include <fstream>
#define M 666013
using namespace std;
ifstream f("kfib.in");
ofstream g("kfib.out");
typedef long long mat[3][3];
mat p,a;
void prod(mat &x,mat y)
{
    mat z,t;
    z[1][1]=x[1][1];
    z[1][2]=x[1][2];
    z[2][1]=x[2][1];
    z[2][2]=x[2][2];
    t[1][1]=y[1][1];
    t[1][2]=y[1][2];
    t[2][1]=y[2][1];
    t[2][2]=y[2][2];
    x[1][1]=(z[1][1]*t[1][1]+z[1][2]*t[2][1])%M;
    x[1][2]=(z[1][1]*t[1][2]+z[1][2]*t[2][2])%M;
    x[2][1]=(z[2][1]*t[1][1]+z[2][2]*t[2][1])%M;
    x[2][2]=(z[2][1]*t[1][2]+z[2][2]*t[2][2])%M;
}
int n;
int main()
{
    a[1][1]=a[1][2]=a[2][1]=1;
    a[2][2]=0;
    p[1][1]=p[2][2]=1;
    p[1][2]=p[2][1]=0;
    f>>n;
    while(n)
    {
        if(n%2==1)
            prod(p,a);
        prod(a,a);
        n=n/2;
    }
    g<<p[1][2];
    return 0;
}