#include <iostream>
#include <fstream>
#define mod 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long a[2][2]={{0, 1}, {1, 1}};
long long b[2][2]={{1, 0}, {0, 1}};
int n;
void inmultire() {
    long long aux[2][2], sum = 0;
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= 1; j++) {
            sum = 0;
            for (int k = 0; k <= 1; k++) {
                sum = (sum + a[i][k] * b[k][j]) % mod;
            }
            aux[i][j] = sum;
        }
    }
    b[0][0] = aux[0][0];
    b[0][1] = aux[0][1];
    b[1][0] = aux[1][0];
    b[1][1] = aux[1][1];
}
void inmultireSine() {
    long long sum = 0;
    long long aux[2][2];
    for (int i = 0; i <= 1; i++) {
        for (int j = 0; j <= 1; j++) {
            sum = 0;
            for (int k = 0; k <= 1; k++) {
                sum = (sum + a[i][k] * a[k][j]) % mod;
            }
            aux[i][j] = sum;
        }
    }
    a[0][0] = aux[0][0];
    a[0][1] = aux[0][1];
    a[1][0] = aux[1][0];
    a[1][1] = aux[1][1];
}
int main()
{
    fin>>n;
    n++;
    while(n) {
        if(n&1) {
            inmultire();
        }
        inmultireSine();
        n = n>>1;
    }
    fout<<b[0][0];
    /*
    for(int i = 0; i <= 1; i++) {
        for(int j = 0; j <= 1; j++) {
            cout<<b[i][j]<<' ';
        }
        cout<<'\n';
    }
    */
    fin.close();
    fout.close();
    return 0;
}