#include <bits/stdc++.h>
#define mod 666013
using namespace std;

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

int n;
long long A[4], rez[4], temp[4];


void inm(int n){
    if (n == 1)
        return;
    else if (n % 2 == 1){
        inm(n-1);
        temp[0] = rez[0];
        temp[1] = rez[1];
        temp[2] = rez[2];
        temp[3] = rez[3];
        rez[0] = A[0] * temp[0] + A[1] * temp[2];
        rez[0] %= mod;
        rez[1] = A[0] * temp[1] + A[1] * temp[3];
        rez[1] %= mod;
        rez[2] = A[2] * temp[0] + A[3] * temp[2];
        rez[2] %= mod;
        rez[3] = A[2] * temp[1] + A[3] * temp[3];
        rez[3] %= mod;
    }
    else {
        inm(n / 2); 
        temp[0] = rez[0];
        temp[1] = rez[1];
        temp[2] = rez[2];
        temp[3] = rez[3];
        rez[0] = temp[0] * temp[0] + temp[1] * temp[2];
        rez[0] %= mod;
        rez[1] = temp[0] * temp[1] + temp[1] * temp[3];
        rez[1] %= mod;
        rez[2] = temp[2] * temp[0] + temp[3] * temp[2];
        rez[2] %= mod;
        rez[3] = temp[2] * temp[1] + temp[3] * temp[3];
        rez[3] %= mod;
    }
}


int main()
{
// matricea ( 0  1 
//            1 1)
// trb sa facem A^n
fin>>n;
A[0] = 0;
A[1] = 1;
A[2] = 1;
A[3] = 1;
rez[0] = 0;
rez[1] = 1;
rez[2] = 1;
rez[3] = 1;
inm(n);
fout << rez[2];
// logn * 8
    return 0;
}