#include <fstream>
#include <vector>

using namespace std;

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

const int MOD = 666013;

struct mat_1x2
{
    int a[2][3];
};

struct mat_2x2
{
    int a[3][3];
};

mat_1x2 Product(mat_1x2 a, mat_2x2 b)
{
    mat_1x2 rez;
    rez.a[1][1] = 0;
    rez.a[1][2] = 0;

    for(int j = 1; j <= 2; j++)
        for(int k = 1; k <= 2; k++)
            rez.a[1][j] = (rez.a[1][j] + (1LL * a.a[1][k] * b.a[k][j] % MOD)) % MOD; 
    
    return rez;
}

mat_2x2 Product(mat_2x2 a, mat_2x2 b)
{
    mat_2x2 rez;
    rez.a[1][1] = 0;
    rez.a[1][2] = 0;
    rez.a[2][1] = 0;
    rez.a[2][2] = 0;

    for(int i = 1; i <= 2; i++)
        for(int j = 1; j <= 2; j++)
            for(int k = 1; k <= 2; k++)
                rez.a[i][j] = (rez.a[i][j] + (1LL * a.a[i][k] * b.a[k][j] % MOD)) % MOD; 
    
    return rez;
}

mat_2x2 Power(mat_2x2 a, int b)
{
    mat_2x2 rez;
    rez.a[1][1] = 1;
    rez.a[1][2] = 0;
    rez.a[2][1] = 0;
    rez.a[2][2] = 1;

    while(b)
    {
        if(b % 2 == 1)
            rez = Product(rez, a);
        a = Product(a, a);
        b /= 2;
    }

    return rez;
}

int n;

int main()
{
    cin >> n;

    mat_1x2 M;
    M.a[1][1] = 0;
    M.a[1][2] = 1;

    mat_2x2 Z;
    Z.a[1][1] = 0;
    Z.a[1][2] = 1;
    Z.a[2][1] = 1;
    Z.a[2][2] = 1;

    Z = Power(Z, n - 1);

    mat_1x2 ans = Product(M, Z);
    cout << ans.a[1][2];

    return 0;
}