#include <fstream>
#include <cstring>
#define modulo 666013
using namespace std;
class matrice
{
    unsigned int a[2][2];
    public:
    void set_mat(unsigned int x,unsigned int y,unsigned int z,unsigned int t)
    {
        a[0][0]=x;a[0][1]=y;a[1][0]=z;a[1][1]=t;
    }
    friend matrice operator*(matrice,matrice);
    unsigned int get_rez()
    {
        return a[0][1];
    }
};
matrice operator*(matrice A,matrice B)
{
    matrice C;
    unsigned int i,j,k;
    for (i=0;i<=1;i++)
    {
        for (j=0;j<=1;j++)
        {
            C.a[i][j]=0;
            for (k=0;k<=1;k++)
            {
                C.a[i][j]+=A.a[i][k]*B.a[k][j];
                C.a[i][j]%=modulo;
            }
        }
    }
    return C;
}
int main()
{
    ifstream f("kfib.in");
    ofstream g("kfib.out");
    unsigned int k;
    f>>k;
    matrice A,R;k-=2;
    A.set_mat(0,1,1,1);
    R.set_mat(1,0,0,1);
    while (k)
    {
        if (k%2) R=R*A;
        A=A*A;
        k/=2;
    }
    A.set_mat(1,1,0,0);
    A=A*R;
    g<<A.get_rez()<<'\n';
    f.close();
    g.close();
    return 0;
}