import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = new FileInputStream("kfib.in");
        OutputStream outputStream = new FileOutputStream("kfib.out");

        try (InputReader inputReader = new InputReader(inputStream);
            PrintWriter printWriter = new PrintWriter(outputStream)) {

            printWriter.println(Solver.findFib(inputReader.nextInt()));
        }

    }

    static class Solver {

        public static int findFib(int N) {
            SquareMatrix fibonacciSeq = new SquareMatrix(new int[][]{
                    {1, 1},
                    {0, 0}
            });

            SquareMatrix fibonacciRecurrence = new SquareMatrix(new int[][] {
                    {0, 1},
                    {1, 1}});

            fibonacciRecurrence = fibonacciRecurrence.pow(N - 2);
            fibonacciSeq = fibonacciSeq.multiplyOther(fibonacciRecurrence);

            return fibonacciSeq.get(0, 1);
        }
    }

    static class SquareMatrix {

        private static final int MOD = 666013;

        private int N;

        private int[][] data;

        public SquareMatrix(int N) {
            this.N = N;
            this.data = new int[N][N];
            for (int i = 0; i < N; i++) {
                Arrays.fill(data[i], 0);
            }
        }

        public SquareMatrix(int[][] data) {
            for (int i = 0; i < data.length; i++) {
                assert(data.length == data[i].length);
            }
            this.N = data.length;
            this.data = data;
        }

        public SquareMatrix copyMatrix() {
            SquareMatrix copy = new SquareMatrix(N);
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < N; col++) {
                    copy.set(row, col, get(row, col));
                }
            }

            return copy;
        }

        public static SquareMatrix neutralElementMultiplication(int N) {
            SquareMatrix matrix = new SquareMatrix(N);
            for (int i = 0; i < N; i++) {
                matrix.set(i, i, 1);
            }
            return matrix;
        }

        private void set(int row, int col, int value) {
            data[row][col] = value;
        }

        public int get(int row, int col) {
            return data[row][col];
        }

        public SquareMatrix multiplyOther(SquareMatrix other) {
            assert(N == other.N);
            SquareMatrix result = new SquareMatrix(N);
            for (int row = 0; row < N; row++) {
                for (int col = 0; col < N; col++) {
                    long newValue = 0;
                    for (int k = 0; k < N; k++) {
                        newValue += ((long) get(row, k) * other.get(k, col)) % MOD;
                        if (newValue >= MOD) {
                            newValue -= MOD;
                        }
                    }

                    result.set(row, col, (int) newValue);
                }
            }

            return result;
        }

        public SquareMatrix pow(int exp) {
            SquareMatrix result = neutralElementMultiplication(N);
            SquareMatrix currMatrixPowerOfTwo = copyMatrix();
            while (exp != 0) {
                if (exp % 2 == 1) {
                    result = result.multiplyOther(currMatrixPowerOfTwo);
                }
                currMatrixPowerOfTwo = currMatrixPowerOfTwo.multiplyOther(currMatrixPowerOfTwo);
                exp /= 2;
            }

            return result;
        }

        @Override
        public String toString() {
            return Arrays.deepToString(data);
        }
    }

    static class InputReader implements AutoCloseable {

        private BufferedReader bufferedReader;

        private StringTokenizer stringTokenizer;

        public InputReader(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = null;
        }

        private String nextToken() {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return stringTokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        @Override
        public void close() throws IOException {
            bufferedReader.close();
        }
    }
}