Large Fibonacci Number Modulo

The Fibonacci numbers start with 0 and 1. The 0th Fibonacci number is 0 and the 1st Fibonacci number is 1. From the 2nd one on, each Fibonacci number is the sum of the two that come right before it.

As a formula, $F_n = F_{n-1} + F_{n-2}$ ($n \ge 2$).

Listing the Fibonacci numbers up to $n = 17$ gives:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

Given $n$, write a program that computes the $n$th Fibonacci number.

The first line contains $n$. $n$ is a natural number less than or equal to 1,000,000,000,000,000,000.

Print the remainder of the $n$th Fibonacci number divided by 1,000,000,007 on the first line.