#include <iostream>
#include <fstream>

using namespace std;

ifstream f("kfib.in");
ofstream g("kfib.out");

const int mod = 666013;

void InmultireMatrice(int a[][2], int b[][2])
{
    int c[3][3];
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
        {
            c[i][j] = 0;
            for (int k = 0; k < 2; k++)
                c[i][j] = (c[i][j] + (1LL * a[i][k] * b[k][j])%mod) % mod;
        }
    }
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            a[i][j] = c[i][j];
    
}

int main() 
{
    int p;
    f >> p;
    p--;
    
    int x[2][2]= {
        {1, 0},
        {0, 1}
    };
    int v[2][2] = {
        {0, 1},
        {1, 1}
    };
    
    int rez[2][1] = {
        {0},
        {1},
    };
    
    unsigned int i = 1;
    while (i <= p)
    {
        if ((i & p) != 0)
        {
            //cout << i << '\n';
            // x *= v
            InmultireMatrice(x, v);
        }
        // v *= v
        InmultireMatrice(v, v);
        i <<= 1;
    }
    
    g << x[1][1];
    
    return 0;
}