#include <iostream>
#include <fstream>
using namespace std; //1 1 2 3 5 ...
void power(int Z[2][2], int x)
{
    int Z0[2][2];
    Z0[0][0] = Z[0][0];
    Z0[1][0] = Z[1][0];
    Z0[0][1] = Z[0][1];
    Z0[1][1] = Z[1][1];

    while(x>1)
    {
        int Z1[2][2];
        Z1[0][0] = Z[0][0];
        Z1[1][0] = Z[1][0];
        Z1[0][1] = Z[0][1];
        Z1[1][1] = Z[1][1];

        Z[0][0] = Z1[0][0]*Z0[0][0] + Z1[0][1]*Z0[1][0];

        Z[0][1] = Z1[0][0]*Z0[0][1] + Z1[0][1]*Z0[1][1];

        Z[1][0] = Z1[1][0]*Z0[0][0] + Z1[1][1]*Z0[1][0];

        Z[1][1] = Z1[1][0]*Z0[0][1] + Z1[1][1]*Z0[1][1];

        x--;
    }

}
int fibonacci(int Z[2][2], int k)
{
    if(k)
    {
        if(k%2==0)
        {
            power(Z,2);
            fibonacci(Z,k/2);
        }
        else
        {
            bool felt = true;
            for(int i=3;i<k/2 && felt;i+=2)
            {
                if(k%i==0)
                {
                    felt = false;
                    power(Z,i);
                    fibonacci(Z,k/i);
                }
            }
            if(felt)
            {
                power(Z,k);
                return Z[0][1]%666013;
            }
        }
    }
    else
    {
        power(Z,k);
        return Z[0][1]%666013;
    }
}
int main()
{
    ifstream in("kfib.in");
    ofstream out("kfib.out");
    int Z[2][2]={0,1,1,1};
    int k;
    in>>k;
    out << fibonacci(Z,k);
    return 0;
}