#include <fstream>
#define MOD 666013
using namespace std;

ifstream fin ("kfib.in");
ofstream fout ("kfib.out");
long long n,a[4][4],sol[4][4],x[4][4];
void produs (long long a[4][4],long long b[4][4],long long c[4][4]){
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++){
            c[i][j] = 0;
            for (int k=1;k<=2;k++){
                c[i][j] += (a[i][k] * b[k][j] * 1LL) % MOD;
                c[i][j] %= MOD;
            }
        }
}
void copiere (long long a[4][4],long long b[4][4]){
    for (int i=1;i<=2;i++)
        for (int j=1;j<=2;j++)
            a[i][j] = b[i][j];
}
int main (){

    fin>>n;
    if (n <= 1)
        fout<<n;
    n--;
    a[1][1] = a[1][2] = a[2][1] = 1;
    sol[1][1] = sol[2][2] = 1;
    while (n){
        if (n%2 == 1){
            produs (a,sol,x);
            copiere (sol,x);
        }
        produs (a,a,x);
        copiere (a,x);
        n/=2;
    }
    fout<<sol[1][1];



    return 0;
}