#include <iostream>
#include <fstream>

const int MOD = 666013;

//a = b * c
void multiply(long long a[2][2], long long b[2][2], long long c[2][2]){
    long long res[2][2];
    res[0][0] = res[1][0] = res[0][1] = res[1][1] = 0;

    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            for(int k = 0; k < 2; k++){
                res[i][j] = ((res[i][j] % MOD) +  ((b[i][k] % MOD) * (c[k][j] % MOD)) % MOD) % MOD;
            }
        }
    }

    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            a[i][j] = res[i][j];
        }
    }
}

//a = b ^ n
void power(long long a[2][2], long long b[2][2], int n){
    long long res[2][2];
    res[0][0] = res[1][1] = 1;
    res[0][1] = res[1][0] = 0;

    while(n > 0){
        if(n % 2 == 0){
            multiply(b, b, b);
            n /= 2;
        }else{
            multiply(res, res, b);
            n--;
        }
    }

    for(int i = 0; i < 2; i++){
        for(int j = 0; j < 2; j++){
            a[i][j] = res[i][j];
        }
    }
}

int main(){
    std::ifstream fin("kfib.in");
    std::ofstream fout("kfib.out");

    int n;
    long long a[2][2], b[2][2];
    a[0][0] = 0;
    a[0][1] = a[1][0] = a[1][1] = 1;
    fin >> n;

    if(n == 0){
        fout << 0;
    }else if(n == 1){
        fout << 1;
    }else{
        power(b, a, n - 1);

        fout << b[1][1];
    }

    fin.close();
    fout.close();
    return 0;
}