// Description
Output the n-th Fibonacci number modulo 1000000007, where F(1) = F(2) = 1.
// Input
A single integer n (1 <= n <= 10^9).
// Output
A single integer: F(n) mod 1000000007.
// Hint
Use fast doubling or matrix exponentiation for large n.