public class Main {
	public static final long MOD = 1000000007;
	public static void main(String[] args) {
		fib1(10000000);
		fib2(10000000);
	}
	
	public static void fib1(int n) {
		long stime = System.nanoTime();
		long[] fib = new long[n+1];
		fib[0] = 0; fib[1] = 1;
		for(int i=2;i<=n;i++) {
			fib[i] = (fib[i-2] + fib[i-1]) % MOD;
		}
		System.out.println((System.nanoTime() - stime) / 1000000 + " ms");
		System.out.println(fib[n]);
	}
	public static void fib2(int n) {
		long stime = System.nanoTime();
		long[] fib = new long[n+1];
		fib[0] = 0; fib[1] = 1;
		for(int i=2;i<=n;i++) {
			fib[i] = fib[i-2] + fib[i-1];
			if (fib[i] >= MOD) fib[i] -= MOD;
		}
		System.out.println((System.nanoTime() - stime) / 1000000 + " ms");
		System.out.println(fib[n]);
	}
}