#include <bits/stdc++.h>

using namespace std;

ifstream f ("kfib.in");
ofstream g ("kfib.out");

const int MOD = 666013;

struct MAT{
    int mat[2][2];
};

MAT nullMat = {{
  {1, 0},
  {0, 1}
}};

MAT initMat = {{
    {0, 0},
    {1, 0}
}};

MAT prodMat = {{
    {0, 1},
    {1, 1}
}};

MAT prod(MAT a, MAT b){
    
    MAT aux;
    aux = {{
      {0, 0},
      {0, 0}
    }};
    
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++){
            
            long long sum = 0;
            
            for(int k=0; k<2; k++)
                sum = (long long)(sum + (long long)a.mat[i][k] * b.mat[k][j] % MOD) % MOD;
                
            aux.mat[i][j] = sum;
            
        }
    }
    
    return aux;
    
}

MAT pwr(MAT a, int n){
    
    if(n == 0)
        return nullMat;
    
    if(n % 2 == 0)
        return pwr(prod(a, a), n/2);
    
    return prod(a, pwr(prod(a, a), n/2));
    
}

int main()
{
    int n;
    f >> n;
    
    if(n == 0){
        g << 0;
        return 0;
    }
    
    g << prod(pwr(prodMat, n-1), initMat).mat[1][0];

    return 0;
}