#include <iostream>
#include <fstream>
#define MOD 666013

using namespace std;

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

int n;

void multiply(int F[2][2], int M[2][2])
{
   int x = (1LL * F[0][0]*M[0][0] + 1LL * F[0][1]*M[1][0]) % MOD;
   int y = (1LL * F[0][0]*M[0][1] + 1LL * F[0][1]*M[1][1]) % MOD;
   int z = (1LL * F[1][0]*M[0][0] + 1LL * F[1][1]*M[1][0]) % MOD;
   int w = (1LL * F[1][0]*M[0][1] + 1LL * F[1][1]*M[1][1]) % MOD;

        F[0][0] = x;
        F[0][1] = y;
         F[1][0] = z;
         F[1][1] = w;
}

void power (int f[2][2] , int n)
{
    if (n == 0 || n == 1)
        return;
    int m[2][2] = {{1 , 1} , {1 , 0}};

    power (f , n / 2);
    multiply (f , f);
    if (n % 2 != 0)
        multiply (f , m);
}

int fib (int n)
{
    int f[2][2] = {{1 , 1} , {1 , 0}};
    if (n == 0 || n == 1)
        return 1;
    power (f , n - 1);
    return f[0][0];
}


int main()
{
    f >> n;
    g << fib (n);
    return 0;
}