#include <iostream>
#include <fstream>

using namespace std;

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

void A_n(long long b[4], long long k){
    long long a[4];
    if(k == 1){
        b[0] = 0;
        b[1] = b[2] = b[3] = 1;
    } else {
        if(k % 2 == 0) {
                A_n(b, k/2);
                a[0] = (b[0] * b[0] + b[1] * b[2]) % 666013;
                a[1] = (b[0] * b[1] + b[1] * b[3]) % 666013;
                a[2] = (b[2] * b[0] + b[3] * b[2]) % 666013;
                a[3] = (b[2] * b[1] + b[3] * b[3]) % 666013;
                b[0] = a[0];
                b[1] = a[1];
                b[2] = a[2];
                b[3] = a[3];
            } else {
                A_n(b, k - 1);
                a[0] = b[1];
                a[1] = (b[0] + b[1]) % 666013;
                a[2] = b[3];
                a[3] = (b[2] + b[3]) % 666013;
                b[0] = a[0];
                b[1] = a[1];
                b[2] = a[2];
                b[3] = a[3];
            }
        }
    }

int main()
{
    long long b[4], k;
    fin>>k;
    A_n(b, k-1);
    fout<<b[3] % 666013;
    return 0;
}