import java.io.*;

/**
 * Created by elizabethkim on 12/7/15.
 */
public class Main {

    public void fib() throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("kfib.in"));
        int n = Integer.parseInt(br.readLine());
        br.close();
        if(n < 0 || n > 1000000000) {
            throw new IllegalArgumentException("the input should be between 0 and a billion");
        }
        FourFourMatrix matrix = powerOf(new FourFourMatrix(0, 1, 1, 1), n);

        BufferedWriter bw = new BufferedWriter(new FileWriter("kfib.out"));
        String result = String.valueOf((matrix.e12)%666013);
        bw.write(result);
        bw.close();
    }

    public FourFourMatrix powerOf(FourFourMatrix matrix, int n) {

        if(n == 0) {
            return new FourFourMatrix(1, 0 , 0 ,1);
        }

        if(n == 1) {
            return matrix;
        }

        FourFourMatrix halfResult = powerOf(matrix, n/2);
        FourFourMatrix result = multiply(halfResult, halfResult);

        if(n%2 == 1) {
            return multiply(result, matrix);
        }

        return result;
    }

    private FourFourMatrix multiply(FourFourMatrix m1, FourFourMatrix m2) {
        FourFourMatrix result = new FourFourMatrix();
        result.e11 = moduloOperator(m1.e11, m2.e11, m1.e12, m2.e21);
        result.e12 = moduloOperator(m1.e11, m2.e12, m1.e12, m2.e22);
        result.e21 = moduloOperator(m1.e21, m2.e11, m1.e22, m2.e21);
        result.e22 = moduloOperator(m1.e21, m2.e12, m1.e22, m2.e22);
        //System.out.println(m1.toString());
        return result;
    }

    private int moduloOperator(int a, int b, int c, int d) {
        return (int)((((long) a)*((long) b)) % 666013 + (((long) c)*((long)d)) % 666013) % 666013;
    }

    private class FourFourMatrix {
        private int e11;
        private int e12;
        private int e21;
        private int e22;

        public FourFourMatrix(int e11, int e12, int e21, int e22) {
            this.e11 = e11;
            this.e12 = e12;
            this.e21 = e21;
            this.e22 = e22;
        }

        public FourFourMatrix() {
            this.e11 = 1;
            this.e12 = 0;
            this.e21 = 0;
            this.e22 = 1;
        }

        @Override
        public String toString() {
          return "Matrix: " + e11 + " ," + e12 + " ," + e21 + " ," + e22;
        }
    }

    public static void main(String[] args) throws IOException {

        Main f = new Main();
        f.fib();

    }
}