#include <fstream>
#include <cstring>
#define modulo 666013
using namespace std;
class matrice
{
    long long a[2][2];
    public:
    void set_mat(long long x,long long y,long long z,long long t)
    {
        a[0][0]=x;a[0][1]=y;a[1][0]=z;a[1][1]=t;
    }
    friend matrice operator*(matrice,matrice);
    long long get_rez()
    {
        return a[0][1];
    }
};
matrice operator*(matrice A,matrice B)
{
    matrice C;
    long long 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");
    long long k;
    f>>k;
    matrice A,R;k-=2;
    A.set_mat(0,1,1,1);
    R.set_mat(1,1,0,0);
    while (k)
    {
        if (k%2) R=R*A;
        A=A*A;
        k/=2;
    }
    g<<R.get_rez()<<'\n';
    f.close();
    g.close();
    return 0;
}