#include <fstream>

using namespace std;

#define MOD 666013
typedef long long ll;

ifstream cin("kfib.in");
ofstream cout("kfib.out");

ll matrix[2][2] = {{0, 1},{1, 1}}, ans[2][2] ={{0, 1},{1, 1}};

void solve(ll a[2][2], ll b[2][2], ll (&c)[2][2])
{
    ll d[2][2];
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++) {
            d[i][j] = 0;
            for (int k = 0; k < 2; k++)
                d[i][j] = (d[i][j] + (a[i][k] * b[k][j]) % MOD) % MOD;
        }

    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            c[i][j] = d[i][j];
}

void pow(int p)
{
    while(p)
    {
        if(p & 1)
            solve(ans, matrix, ans);
        solve(matrix, matrix, matrix);
        p /= 2;
    }
}

int n;

int main()
{
    cin >> n;
    pow(n);
    cout << ans[0][0];
    return 0;
}