#include <fstream>

using namespace std;

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

long long a, b = 1, c = 1, d = 1, aux_1, aux_2, aux_3, aux_4, r_1 = 1, r_2 = 0, r_3 = 0, r_4 = 1;

long long solve (int k)
{
    k--;
    while ( k )
    {
        if ( k % 2 == 0 )
        {
            aux_1 = a * a + b * c;
            aux_2 = b * a + b * d;
            aux_3 = a * c + c * d;
            aux_4 = b * c + d * d;
            a = aux_1 % 66601;
            b = aux_2 % 66601;
            c = aux_3 % 66601;
            d = aux_4 % 66601;
            k /= 2;
        }
        else
        {
            aux_1 = r_1 * a + r_2 * b;
            aux_2 = r_1 * b + r_2 * d;
            aux_3 = r_3 * a + r_4 * c;
            aux_4 = r_3 * b + r_4 * d;
            r_1 = aux_1 % 66601;
            r_2 = aux_2 % 66601;
            r_3 = aux_3 % 66601;
            r_4 = aux_4 % 66601;
            k--;
        }
    }
    return r_4;
}

int main()
{
    int k;
    fin>>k;
    if ( k == 0 )
        fout<<"0";
    else
    {
        fout<<solve(k);
    }
}