#include <fstream>

using namespace std;

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

long long A[2];
long long B[2][2];
long long D[2][2];
long long C[2];

int main()
{
    for (int i=0; i<=1; i++)
    {
        A[i]=1;
        for (int y=0; y<=1; y++)
        {
            B[i][y]=1;
            if (i==0 && y==0)
            {
                B[i][y]=0;
            }
        }
    }
    /*for (int i=0; i<=1; i++){
        for (int y=0; y<=1; y++){
            cout<<B[i][y]<<" ";
            if (y==1){
                cout<<'\n';
            }
        }
    }*/
    int m;
    cin>>m;
    m=m-1;
    while (m)
    {
        if (m%2==1)
        {
            for (int i = 0; i <= 1 ; ++ i)
            {
                for (int k = 0; k <= 1; ++ k)
                {
                    C [i] += ((A [k] % 666013)* (B [k][i] % 666013)) % 666013 ;
                }
            }
            for (int i=0; i<=1; i++)
            {
                A[i]=C[i] % 666013;
                C[i]=0;
            }
        }
        for (int i = 0; i <= 1 ; ++ i)
        {
            for (int j = 0 ; j <= 1; ++ j)
            {
                for (int k = 0; k <= 1; ++ k)
                {
                    D [i][j] += ((B [i][k] % 666013) * (B [k][j] % 666013))  % 666013 ;
                }
            }
        }
        for (int i=0; i<=1; i++)
        {
            for (int y=0; y<=1; y++)
            {
                B[i][y]=D[i][y]  % 666013;
                D[i][y]=0;
            }
        }
        m=m/2;
    }
    cout<<A[0];
    return 0;
}