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

long long n, mat[5][5], a[5][5];

void inmultire(long long mat[][5], long long a[][5])
{
    long long aux[5][5] = {0};
    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            for(int k = 1; k <= 2; k++)
                aux[i][j] = (aux[i][j] + (mat[i][k] * a[k][j]) % MOD) % MOD;
    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            mat[i][j] = aux[i][j];
}

int main()
{
    freopen("kfib.in", "r", stdin);
    freopen("kfib.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    mat[1][1] = mat[2][2] = 1;
    a[1][2] = a[2][1] = a[2][2] = 1;

    while(n)
    {
        if(n % 2 == 1)
            inmultire(mat, a);
        inmultire(a, a);
        n = n / 2;
    }

    cout << mat[1][2];

    return 0;
}