#include <fstream>
#include <vector>
#define int long long
using namespace std;

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

vector<vector<int>> startmat(2,vector<int>(2,0));

vector<vector<int>> inmult(vector<vector<int>> mat1,vector<vector<int>> mat2){//pt fibo
    vector<vector<int>> mat(2,vector<int>(2,0));

    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        {
            for(int h = 0;h<2;h++)
            {
                    mat[i][j] += (mat1[i][h] * mat2[h][j]) % MOD;
            }
        }
            for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            mat[i][j] %=  666013;
    return mat;
}

vector<vector<int>> fast_pow_mat(vector<vector<int>> mat,int pow)
{

    if(pow == 1)
        return mat;
    if(pow%2==0)
    {
        vector<vector<int>> currmat = fast_pow_mat(mat,pow/2);
        return inmult(currmat,currmat);
    }
    else
    {
        return inmult(fast_pow_mat(mat,pow-1),mat);
    }
}

int32_t main()
{
    startmat[0][0] = 0;
    startmat[1][0] = 1;
    startmat[1][1] = 1;
    startmat[0][1] = 1;
    int n;
    cin>>n;

    vector<vector<int>> matfinal = fast_pow_mat(startmat,n-1);

        /*for(int i=0;i<2;i++)
        {for(int j=0;j<2;j++)
            cout<<matfinal[i][j]<<" ";
         cout<<'\n';
        }*/

    int m2[2] = {1,1};
        int fib1,fib2;
        fib1 = m2[0] * matfinal[0][0] + m2[0] * matfinal[1][0];
        fib2 = m2[1] * matfinal[1][0] + m2[0] * matfinal[1][1];
        cout<<fib1;

    return 0;
}