#include <fstream>

using namespace std;

#define MOD 666013
ifstream cin("kfib.in");
ofstream cout("kfib.out");

int mat[2][2] = {{1,1},{1,0}};

void inm(int mat1[][2], int mat2[][2]) {
    int mat3[2][2];
    mat3[0][0] = (1ll * mat1[0][0] * mat2[0][0] + 1ll * mat1[0][1] * mat2[1][0]) % MOD;
    mat3[0][1] = (1ll * mat1[0][0] * mat2[0][1] + 1ll * mat1[0][1] * mat2[1][1]) % MOD;
    mat3[1][0] = (1ll * mat1[1][0] * mat2[0][0] + 1ll * mat1[1][1] * mat2[1][0]) % MOD;
    mat3[1][1] = (1ll * mat1[1][0] * mat2[0][1] + 1ll * mat1[1][1] * mat2[1][1]) % MOD;
    for (int i = 0; i <= 1; i++) {
            for (int j = 0; j <= 1; j++) {
                mat1[i][j] = mat3[i][j];
            }
    }
}

int main()
{
    int k;
    cin>>k;
    k--;
    int rez[2][2] = {{1,0},{0,1}};
    for (int mask = 1; mask <= k; mask <<= 1) {
        if ((mask & k) != 0) {
            inm(rez, mat);
        }
        inm(mat, mat);
    }
    cout<<rez[0][0];
    return 0;
}