import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	
	long [][] power (long[][] v,int n){
		if (n==0) {
			long[][] res = new long[v.length][v.length];
			for (int i = 0;i<v.length;i++)
				res[i][i] = 1;
			return res;
		}
		else if (n%2 == 1){
			long[][] p = power(v,(n-1)/2);
			long [][]d = new long[v.length][v.length];
			long [][]sol = new long[v.length][v.length];
			for (int i = 0;i<v.length;i++)
				for (int j = 0;j<v.length;j++)
					for (int k = 0;k<v.length; k++)
						d[i][j] = (d[i][j] + p[i][k] *p[k][j])%666013;
			for (int i = 0;i<v.length;i++)
				for (int j = 0;j<v.length;j++)
					for (int k = 0;k<v.length; k++)
						sol[i][j] = (sol[i][j] +d[i][k] *v[k][j])%666013;
			return sol;
		}
		else {		long [][] p = power(v,(n)/2);
		long [][]d = new long[v.length][v.length];
		for (int i = 0;i<v.length;i++)
			for (int j = 0;j<v.length;j++)
				for (int k = 0;k<v.length; k++)
					d[i][j] = (d[i][j] + p[i][k] *p[k][j])%666013;
		return d;
		}
			
	}
public static void main(String[] args) throws IOException {
	Scanner in = new Scanner(new FileReader ("kfib.in"));
	PrintWriter out = new PrintWriter(new FileWriter("kfib.out"));
	int nr = in.nextInt();
	long[][] i = new long[2][2];
	i[0][1] = 1;
	i[1][0] = 1;
	i[1][1] = 1;
	Main p = new Main();
	i = p.power(i, nr-1);
	long []sol = new long[2];
	sol[0] = i[1][0];
	sol[1] = i[1][1];
	out.println(String.valueOf(sol[1]));
	
	in.close();
	out.close();
}
}