//
//  main.cpp
//  noiembrie
//
//  Created by Tereza Oprea on 02/11/2018.
//  Copyright © 2018 Tereza Oprea. All rights reserved.
//

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

using namespace std;

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

long long  k, a[5][5];

void inmultire (long long a[5][5])
{
    long long x, y, z, t;
    x = a[1][1];
    y = a[1][2];
    z = a[2][1];
    t = a[2][2];
    a[1][1] = (x*x%M + y*z%M) %M;
    a[1][2] = (x*y%M + y*t%M) %M;
    a[2][1] = (z*x%M + t*z%M) %M;
    a[2][2] = (z*y%M + t*t%M) %M;
}

void putere (long long  a[5][5], long long n)
{
    if (n == 1)
        return;
    if (n%2 == 0)
    {
        putere (a, n/2);
        inmultire (a);
    }
    else
    {
        putere (a, n/2);
        inmultire (a);
        long long x, y, z, t;
        x = a[1][1];
        y = a[1][2];
        z = a[2][1];
        t = a[2][2];
        a[1][1] = z;
        a[1][2] = t;
        a[2][1] = (x + z) %M;
        a[2][2] = (y + t) %M;
        
    }
}

int main() {
    fin >> k;
    a[1][1] = 0;
    a[1][2] = 1;
    a[2][1] = 1;
    a[2][2] = 1;
    putere (a, k-2);
    fout << (a[1][2] + a[2][2]) %M;
}