#include <iostream>
#include <fstream>

#define MOD 666013

using namespace std;

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


int main()
{
    long long k;
    f >> k;
    k = k - 2;
    if(k < 0)
        g << 1;
    else
    {
        long long  F[2][2], a, b, c, d, res[2][2];
        F[0][0] = 0;
        F[0][1] = 1;
        F[1][0] = 1;
        F[1][1] = 1;
        res[0][0] = 0;
        res[0][1] = 1;
        res[1][0] = 1;
        res[1][1] = 1;
        while (k > 0)
        {
            if (k % 2 == 0)
            {
                a =  (F[0][0]*F[0][0] + F[0][1]*F[1][0]);
                b =  (F[0][0]*F[0][1] + F[0][1]*F[1][1]);
                c =  (F[1][0]*F[0][0] + F[1][1]*F[1][0]);
                d =  (F[1][0]*F[0][1] + F[1][1]*F[1][1]);
                F[0][0] = a % MOD;
                F[0][1] = b % MOD;
                F[1][0] = c % MOD;
                F[1][1] = d % MOD;
                k /= 2;
            }
            else {
                a =  (res[0][0]*F[0][0] + res[0][1]*F[1][0]);
                b =  (res[0][0]*F[0][1] + res[0][1]*F[1][1]);
                c =  (res[1][0]*F[0][0] + res[1][1]*F[1][0]);
                d =  (res[1][0]*F[0][1] + res[1][1]*F[1][1]);
                res[0][0] = a % MOD;
                res[0][1] = b % MOD;
                res[1][0] = c % MOD;
                res[1][1] = d % MOD;
                k--;
            }
        }
        g << res[1][1];
    }
}