#include <iostream>
#include <fstream>

#define k 666013

using namespace std;

void power(long long a[2][2], long long b[2][2], long long c[2][2])
{
    c[0][0] = (a[0][0]*b[0][0] + a[0][1]*b[0][1]) % k;
    c[0][1] = (c[1][0] = a[0][0]*b[0][1] + a[0][1]*b[1][1]) % k;
    c[1][1] = (a[0][1]*b[0][1] + a[1][1]*b[1][1]) % k;
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    long long n;
    long long res[2][2] = {1, 0, 0, 1};
    long long base[2][2] = {1, 1, 1, 0};
    scanf("%lld", &n);
    n -= 1;

    while(n){
        long long aux[2][2];
        if(n % 2){
            power(res, base, aux);
            res[0][0] = aux[0][0];
            res[0][1] = res[1][0] = aux[0][1];
            res [1][1] = aux[1][1];
        }
        n /= 2;
        power(base, base, aux);
        base[0][0] = aux[0][0];
        base[0][1] = base[1][0] = aux[0][1];
        base [1][1] = aux[1][1];
    }

    printf("%lld\n", res[0][0]);

    return 0;
}