#include <bits/stdc++.h>
#define MOD 666013

using namespace std;

struct mat
{
    int a11, a12, a21, a22;
};
mat matMul(mat mat1, mat mat2)
{
    mat ans;

    ans.a11 = (int64_t)mat1.a11 * mat2.a11 % MOD + (int64_t)mat1.a12 * mat2.a21 % MOD;
    ans.a12 = (int64_t)mat1.a11 * mat2.a12 % MOD + (int64_t)mat1.a12 * mat2.a22 % MOD;
    ans.a21 = (int64_t)mat1.a21 * mat2.a11 % MOD + (int64_t)mat1.a22 * mat2.a21 % MOD;
    ans.a22 = (int64_t)mat1.a21 * mat2.a12 % MOD + (int64_t)mat1.a22 * mat2.a22 % MOD;


    return ans;
}


mat fastExp(mat base, int exp)
{
    mat ans = mat{1, 0, 0, 1};

    while (exp > 0)
    {
        if (exp & 1)
            ans = matMul(ans, base);
        exp >>= 1;
        base = matMul(base, base);
    }
    return ans;
}

int main()
{
    int n;
    ifstream fin("kfib.in");
    ofstream fout("kfib.out");
    cin >> n;
    
    
    mat base = mat{1, 1, 1, 0};
    base = fastExp(base, n - 1);
    cout << base.a11 << endl;


    return 0;
}