#include <fstream>

using namespace std;
ifstream cin("kfib.in");
ofstream cout("kfib.out");
const int MOD = 666013;
struct matrice{
    long long m[2][2];
};
void operator *= (matrice& a,matrice b){
    int i,j,k;
    matrice rez;
    for(i = 0;i < 2;i++){
        for(j = 0;j < 2;j++){
            rez.m[i][j] = 0;
            for(k = 0;k < 2;k++){
                rez.m[i][j] += a.m[i][k] * b.m[k][j];
               rez.m[i][j] %= MOD;
            }
        }
    }
      for(i = 0;i < 2;i++)
        for(j = 0;j < 2;j++)
            a.m[i][j] = rez.m[i][j];
}
matrice exp(matrice n,int p){
    matrice rest;
    int i,j;
    for(i = 0;i < 2;i++)
    for(j = 0;j < 2;j++){
        rest.m[i][j] = n.m[i][j];
    }
    while(p)
    {
        if(p % 2)
        {
            rest *= n;
        }
        n *= n;
        p >>= 1;
    }
    return rest;
}
int main()
{
    int n,i,j;
    cin >> n;
    matrice init;
    init.m[0][0] = init.m[1][0] = init.m[0][1] = 1;
    init.m[1][1] = 0;
    cout << exp(init,n  -2).m[0][0] ;
    return 0;
}