#include <fstream>
#include <vector>
#include <algorithm>


using namespace std;

const int mod = 666013;

vector<vector<int>> inmult(vector<vector<int>> A, vector<vector<int>> B){

    vector<vector<int>> res = {
        {0, 0},
        {0, 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] + (long long)A[i][k] * B[k][j]) % mod;

    return res;
}

int main()
{
    ifstream cin("kfib.in");
    ofstream cout("kfib.out");
         

    int K;
    cin >> K;

   vector<vector<int>> mat = {
       {0, 1},
       {1, 1}
   }, sol = {
       {1, 0},
       {0, 1}
   };

   --K;
   while(K > 0){
       if(K % 2){
           sol = inmult(sol, mat);
           --K;
       }
       else{
           mat = inmult(mat, mat);
           K /= 2;
       }   
   }

   cout << sol[1][1];
  
    cin.close();
    cout.close();

    return 0;
}