import java.io.FileInputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
  public static final String IN_FILE = "kfib.in";
  public static final String OUT_FILE = "kfib.out";
  public static final int MOD = 666013;

  public static int[][] multiply(final int[][] a, final int[][] b) {
    final int n = a.length;
    final int m = a[0].length;
    final int p = b[0].length;
    assert(m == b.length);

    final int[][] result = new int[n][p];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < p; j++) {
        for (int k = 0; k < m; k++) {
          result[i][j] = (int) ((result[i][j] + 1L * a[i][k] * b[k][j] ) % MOD);
        }
      }
    }
    return result;
  }

  public static int[][] identity(final int n) {
    assert(n > 0);
    final int[][] identity = new int[n][n];
    for (int i = 0; i < n; i++) {
      identity[i][i] = 1;
    }
    return identity;
  }

  public static int[][] pow(final int[][] a, final int p) {
    final int n = a.length;
    assert(n == a[0].length && p >= 0);
    if (p == 0) {
      return identity(n);
    }
    return p % 2 == 1 ? multiply(a, pow(a, p - 1)) : pow(multiply(a, a), p / 2);
  }

  public static int fibonacci(final int n) {
    final int[][] fib01 = new int[][] {{0}, {1}};
    final int[][] z = new int[][] {{0, 1}, {1, 1}};
    return multiply(pow(z, n), fib01)[0][0];
  }

  public static void main(final String[] args) throws IOException {
    try (final Scanner scanner = new Scanner(new FileInputStream(IN_FILE));
        final PrintWriter writer = new PrintWriter(OUT_FILE)) {
      final int n = scanner.nextInt();
      final int fib = fibonacci(n);
      writer.println(fib);
    }
  }
}