#include <fstream>
#define rest 666013;

using namespace std;

ifstream fin("kfib.in");
ofstream fout("kfib.out");

long long int a[2][2] = { {0 , 1} , {1 , 1} } , b[2][2] = { {1 , 0} , {0 , 1} };
int n;

void Produs(long long int x[2][2], long long int y[2][2])
{
    int z[2][2];
    z[0][0] = (x[0][0]*y[0][0] + x[0][1]*y[1][0])%rest;
    z[0][1] = (x[0][0]*y[0][1] + x[0][1]*y[1][1])%rest;
    z[1][0] = (x[1][0]*y[0][0] + x[1][1]*y[1][0])%rest;
    z[1][1] = (x[1][0]*y[0][1] + x[1][1]*y[1][1])%rest;

    x[0][0] = z[0][0];
    x[0][1] = z[0][1];
    x[1][0] = z[1][0];
    x[1][1] = z[1][1];
}

int main()
{
    fin >> n;
    n++;
    while (n > 1)
    {
        if (n % 2 == 0)
        {
            n /= 2;
            Produs(a, a);
        }
        else
        {
            n--;
            Produs(b, a);
        }
    }
    Produs(a, b);
    fout<<a[0][0];
    return 0;
}