#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 666013;

int mat[2][2], curr[2][2], ans[1][2], aux[2][2];

void inm1(){
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            aux[i][j] = curr[i][j];
    curr[0][0] = aux[0][0] * mat[0][0] + aux[0][1] * mat[1][0];
    curr[0][0] %= mod;
    curr[0][1] = aux[1][0] * mat[0][0] + aux[1][1] * mat[1][0];
    curr[0][1] %= mod;
    curr[1][0] = aux[0][0] * mat[0][1] + aux[0][1] * mat[1][1];
    curr[1][0] %= mod;
    curr[1][1] = aux[1][0] * mat[0][1] + aux[1][1] * mat[1][1];
    curr[1][1] %= mod;
}

void inm2(){
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            aux[i][j] = mat[i][j];
    mat[0][0] = aux[0][0] * aux[0][0] + aux[0][1] * aux[1][0];
    mat[0][0] %= mod;
    mat[0][1] = aux[1][0] * aux[0][0] + aux[1][1] * aux[1][0];
    mat[0][1] %= mod;
    mat[1][0] = aux[0][0] * aux[0][1] + aux[0][1] * aux[1][1];
    mat[1][0] %= mod;
    mat[1][1] = aux[1][0] * aux[0][1] + aux[1][1] * aux[1][1];
    mat[1][1] %= mod;
}

signed main(){
    
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
    
    int n;
    cin >> n;
    if(n == 0){
        cout << 0;
        return 0;
    }
    else if(n == 1){
        cout << 1;
        return 0;
    }
    mat[1][1] = mat[1][0] = mat[0][1] = 1;
    ans[0][1] = 1;
    for(int i = 0; i < 2; i++)
        for(int j = 0; j < 2; j++)
            curr[i][j] = mat[i][j];
    n--;
    while(n){
        if(n & 1)
            inm1();
        inm2();
        n >>= 1;
    }
    cout << curr[1][0];
    
    return 0;
}