#include<fstream>
using namespace std;

#define MAX 666013

class Matrice
{
    unsigned long long mat[2][2];

public:
    Matrice()
    {
        mat[0][0] = 0; mat[0][1] = mat[1][0] = mat[1][1] = 1;
    }

    int get(unsigned char i, unsigned char j)
    {
        return mat[i][j];
    }

    void set(unsigned char i, unsigned char j, unsigned long long val)
    {
        mat[i][j] = val;
    }

    Matrice operator*(Matrice b)
    {
        Matrice rez;
        rez.set(0, 0, (mat[0][0]*b.get(0,0) % MAX + mat[0][1]*b.get(1,0) % MAX) % MAX);
        rez.set(0, 1, (mat[0][0]*b.get(0,1) % MAX + mat[0][1]*b.get(1,1) % MAX) % MAX);
        rez.set(1, 0, (mat[1][0]*b.get(0,0) % MAX + mat[1][1]*b.get(1,0) % MAX) % MAX);
        rez.set(1, 1, (mat[1][0]*b.get(0,1) % MAX + mat[1][1]*b.get(1,1) % MAX) % MAX);

        return rez;
    }

    void operator=(Matrice m)
    {
        unsigned char i, j;

        for(i=0; i<=1; i++)
            for(j=0; j<=1; j++)
                mat[i][j] = m.get(i,j);
    }
};

int main()
{
    unsigned long p;
    unsigned char i;
    Matrice r, b;
    fstream in("kfib.in", fstream::in);
    fstream out("kfib.out", fstream::out);

    in>>p;
    in.close();

    for(i = 0; (unsigned)(1<<i) <= p; i++)
    {
        if((1<<i) & p)
            r = r*b;
        b = b*b;
    }

    out<<r.get(0,0);
    out.close();

    return 0;
}