#include<bits/stdc++.h>
#define MOD 666013
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
vector<vector<long long>> I2;
vector<vector<long long>> matrix_multiplication(vector<vector<long long>> X, vector<vector<long long>> Y){
    vector<vector<long long>> Z;
    Z.push_back({0, 0}),  Z.push_back({0, 0});
    Z[0][0] = ((X[0][0] * Y[0][0]) % MOD + (X[0][1] * Y[1][0]) % MOD) % MOD;
    Z[0][1] = ((X[0][0] * Y[0][1]) % MOD + (X[0][1] * Y[1][1]) % MOD) % MOD;
    Z[1][0] = ((X[1][0] * Y[0][0]) % MOD + (X[1][1] * Y[1][0]) % MOD) % MOD;
    Z[1][1] = ((X[1][0] * Y[0][1]) % MOD + (X[1][1] * Y[1][1]) % MOD) % MOD;
    return Z;
} 
vector<vector<long long>> fast_exponentiation_matrix(vector<vector<long long>> M, int n){
    if(n == 0) return I2;
    else if(n % 2 == 0) return fast_exponentiation_matrix(matrix_multiplication(M, M), n / 2);
    else return matrix_multiplication(M, fast_exponentiation_matrix(matrix_multiplication(M, M), n / 2));
}
int nthfibonacci(int k){
    vector<vector<long long>> M1, Z;
    M1.push_back({0, 1});
    Z.push_back({0, 1}), Z.push_back({1, 1});
    return fast_exponentiation_matrix(Z, k - 1)[1][1]; 
}
int main(){
    int k;
    I2.push_back({1, 0});
    I2.push_back({0, 1});
    fin >> k;
    fout << nthfibonacci(k);
    fin.close();
    fout.close();
    return 0;
}