#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("kfib.in");
ofstream fout("kfib.out");
long long int rez[5][5],c[5][5];
void putlog(long long int b[5][5],long long int e,const long long int mod)
{
    while(e != 0)
    {
        if(e % 2 == 1)
        {
            for(int i = 0; i < 2; i++)
            {
                for(int j = 0; j < 2; j++)
                {
                    c[i][j] = 0;
                    for(int k = 0; k < 2; k++)
                        c[i][j] = (c[i][j] + (rez[i][k] * b[k][j])%mod )%mod;

                }
            }
            for(int i = 0; i < 2; i++)
                for(int j = 0; j < 2; j++)
                    rez[i][j] = c[i][j];
        }
         e /= 2;
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
            {
                c[i][j] = 0;
                for(int k = 0; k < 2; k++)
                    c[i][j] = (c[i][j] + (b[i][k] * b[k][j])% mod)%mod;

            }
        for(int i = 0; i < 2; i++)
            for(int j = 0; j < 2; j++)
                b[i][j] = c[i][j];

    }
}

int main()
{
    long long int k;
    fin >> k;
    long long int b[5][5];
    b[0][0] = 0;
    b[0][1] = 1;
    b[1][0] = 1;
    b[1][1] = 1;

    rez[0][0] = 1;
    rez [0][1] = 0;
    rez[1][0] = 0;
    rez[1][1] = 1;
    putlog(b,k - 1,666013);
    fout << rez[1][1];
    return 0;
}