#include <bits/stdc++.h>

using namespace std;

# define pb push_back
# define mp make_pair
# define FORN( a , b , c ) for ( int a = b ; a <= c ; ++ a )
# define FORNBACK( a , b , c ) for ( int a = b ; a >= c ; -- a )

const int MOD = 666013 ;

pair < pair < int , int > , pair < int , int > > mul ( pair < pair < int , int > , pair < int , int > > A , pair < pair < int , int > , pair < int , int > > B ) {
    int a = A.first.first ;
    int b = A.first.second ;
    int c = A.second.first;
    int d = A.second.second ;
    int e = B.first.first ;
    int f = B.first.second ;
    int g = B.second.first;
    int h = B.second.second ;
    pair < pair < int , int > , pair < int , int > > result ;
    result.first.first =   ( 1LL * a * e % MOD + 1LL * b * g % MOD ) % MOD ;
    result.first.second =  ( 1LL * a * f % MOD + 1LL * b * h % MOD ) % MOD ;
    result.second.first =  ( 1LL * c * e % MOD + 1LL * d * g % MOD ) % MOD ;
    result.second.second = ( 1LL * c * f % MOD + 1LL * d * h % MOD ) % MOD ;
    return result ;
}

pair < pair < int , int > , pair < int , int > > put ( pair < pair < int , int > , pair < int , int > > Z , int K ) {
    pair < pair < int , int > , pair < int , int > > ret ;
    ret.first.first = 1 ;
    ret.second.second = 1 ;
    while ( K ) {
        if ( K % 2 == 1 ) {
            pair < pair < int , int > , pair < int , int > > aux = mul ( ret , Z ) ;
            ret = aux ;
        }
        pair < pair < int , int > , pair < int , int > > aux = mul ( Z , Z ) ;
        Z = aux ;
        K /= 2 ;
    }
    return ret ;
}

int main()
{
    ios :: sync_with_stdio ( false ) ;

    freopen( "kfib.in" , "r" , stdin ) ;
    freopen( "kfib.out" , "w" , stdout ) ;
    int k ;
    cin >> k ;
    pair < pair < int , int > , pair < int , int > > matrice ;
    matrice.first.second = 1 ;
    matrice.second.first = 1 ;
    matrice.second.second = 1 ;
    pair < pair < int , int > , pair < int , int > > finala = put ( matrice , k - 1 ) ;
    cout << ( finala.first.first + finala.second.first ) % MOD ;
    return 0 ;
}