//
//  main.cpp
//  Al k-lea termen Fibonacci (infoarena)
//
//  Created by Andrei Bădulescu on 18.11.22.
//

//#include <iostream>
#include <fstream>

using namespace std;

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

const long long M = 666013;

long long matrix[3][3], rez[3][3];
int n;

int main() {
    cin >> n;
    
    matrix[2][2] = matrix[1][2] = matrix[2][1] = 1;
    rez[2][2] = rez[1][2] = rez[2][1] = 1;
    n--;
    
    long long a, b, c, d;
    
    while (n) {
        if ((n & 1) == 0) {
            n = n / 2;
            
            a = matrix[1][1] * matrix[1][1] + matrix[1][2] * matrix[2][1];
            b = matrix[1][1] * matrix[1][2] + matrix[1][2] * matrix[2][2];
            c = matrix[2][1] * matrix[1][1] + matrix[2][2] * matrix[2][1];
            d = matrix[2][1] * matrix[1][2] + matrix[2][2] * matrix[2][2];
            
            a = a % M;
            b = b % M;
            d = d % M;
            matrix[1][1] = a;
            matrix[1][2] = matrix[2][1] = b;
            matrix[2][2] = d;
        } else {
            n = n - 1;
            
            a = rez[1][1] * matrix[1][1] + rez[1][2] * matrix[2][1];
            b = rez[1][1] * matrix[1][2] + rez[1][2] * matrix[2][2];
            c = rez[2][1] * matrix[1][1] + rez[2][2] * matrix[2][1];
            d = rez[2][1] * matrix[1][2] + rez[2][2] * matrix[2][2];
             
            a = a % M;
            b = b % M;
            c = c % M;
            d = d % M;
            
            rez[1][1] = a;
            rez[1][2] = b;
            rez[2][1] = c;
            rez[2][2] = d;
        }
    }
    
    cout << rez[1][2];
    return 0;
}