#include <iostream>
#include <fstream>

using namespace std;
const int P = 666013;
typedef long long ll;


int main()
{
    ifstream f ("kfib.in");
    ofstream g ("kfib.out");

    int K;
    f >> K;

    ll sol[2][2] = {{1,0}, {0,1}};
    ll a[2][2] = {{1,1}, {1,0}};
    ll tmp[2][2];

    if (K == 0)
        g << 0 << '\n';
    else
    {
        K--;
        while(K)
        {
            if (K & 1)
            {
                for (int i = 0; i < 2; i++)
                for (int j = 0; j < 2; j++)
                    tmp[i][j] = sol[i][0] *a[0][j] + sol[i][1] *a[1][j];

                for (int i = 0; i < 2; i++)
                for (int j = 0; j < 2; j++)
                    sol[i][j] = tmp[i][j] %P;
            }

            for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                tmp[i][j] = a[i][0] *a[0][j] + a[i][1] *a[1][j];

            for (int i = 0; i < 2; i++)
            for (int j = 0; j < 2; j++)
                a[i][j] = tmp[i][j] %P;
            K /= 2;
        }
        g << sol[0][0] << '\n';
    }

    return 0;
}