#include <iostream>
#include <fstream>
#define nl '\n'

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

long long int mat[2][2][2], M;  ///0 ans, 1 base

void multiply(int fs, int sc, long long int MOD)
{
    long long int x = mat[fs][0][0]*mat[sc][0][0]+mat[fs][0][1]*mat[sc][1][0];
    long long int y = mat[fs][0][0]*mat[sc][0][1]+mat[fs][0][1]*mat[sc][1][1];
    long long int z = mat[fs][1][0]*mat[sc][0][0]+mat[fs][1][1]*mat[sc][1][0];
    long long int w = mat[fs][1][0]*mat[sc][0][1]+mat[fs][1][1]*mat[sc][1][1];
    x%=MOD;
    y%=MOD;
    z%=MOD;
    w%=MOD;
    mat[fs][0][0] = x;
    mat[fs][0][1] = y;
    mat[fs][1][0] = z;
    mat[fs][1][1] = w;
    return;
}
void binexp(long long int pow, long long int MOD)
{
    mat[1][0][0] = mat[1][0][1] = mat[1][1][0] = 1;
    mat[1][1][1] = 0;
    mat[0][0][0] = mat[0][1][1] = 1;
    mat[0][0][1] = mat[0][1][0] = 0;
    while (pow)
    {
        if (pow&1)
            multiply(0, 1, MOD);
        multiply(1, 1, MOD);
        pow>>=1;
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long int n;
    fin >> n;
    if (n == 1)
    {
        fout << 0;
        return 0;
    }
    binexp(n-1, 666013);
    fout << mat[0][0][0] << nl;
    return 0;
}