#include<stdio.h>
#define mod 666013
#define ll long long
ll Y[2][2] = {1,0,0,1}, Z[2][2] = {0,1,1,1};
FILE *inputFile = fopen("kfib.in", "r"), *outputFile = fopen("kfib.out", "w");
void afisareMatrice(ll m[2][2])
{
    int i,j;
    
    for(i=0;i<2;i++)
    {
        for(j=0;j<2;j++)
            fprintf(outputFile, "%lld ", m[i][j]);
        
        fprintf(outputFile, "\n");
    }
    fprintf(outputFile, "\n");
}
void inmultire(ll A[2][2], ll B[2][2], ll C[2][2])
{
    ll AUXA[2][2] = { A[0][0], A[0][1], A[1][0], A[1][1]},
    AUXB[2][2] = { B[0][0], B[0][1], B[1][0], B[1][1]};
    
    C[0][0] = (AUXA[0][0] * AUXB[0][0] + AUXA[0][1] * AUXB[0][1]) % mod;
    C[0][1] = (AUXA[0][0] * AUXB[0][1] + AUXA[0][1] * AUXB[1][1]) % mod;
    C[1][0] = (AUXA[1][0] * AUXB[0][0] + AUXA[1][1] * AUXB[0][1]) % mod;
    C[1][1] = (AUXA[1][0] * AUXB[0][1] + AUXA[1][1] * AUXB[1][1]) % mod;
   
}
void exp(ll putere, ll matrice[2][2])
{
    while(putere > 1)
        if(putere % 2 == 0)
        {
            putere /= 2;
            inmultire(matrice, matrice, matrice);
        }
        else
        {
            putere = (putere - 1) / 2;
            inmultire(Y, matrice, Y);
            inmultire(matrice, matrice, matrice);
        }
    
    inmultire(Y, matrice, matrice);
}
int main()
{
    
    
    ll n, A[2][2] = {0,1,0,0}, B[2][2] = {0,1,1,1}, C[2][2] = {0};
    
    fscanf(inputFile, "%lld", &n);
    
    //Mn = M1 * Z^(n-1)
  
    
    exp(n-1,B);
    
    inmultire(A, B, C);
    
    fprintf(outputFile, "%lld", C[0][1]);
    
    return 0;
}