819. Tiling Problem — Count Ways to Tile 2×N Floor (Modulo 10^9+7)

Count the number of ways to tile a 2×N floor using 1×2 dominoes, mod 10^9+7. This equals the (N+1)-th Fibonacci number. f(0)=1, f(1)=1, f(n)=f(n-1)+f(n-2).

Input: A non-negative integer n.

Output: Integer mod 10^9+7.

Examples

Input: 3
Output: 3
Explanation: 3 tilings of 2×3.

Input: 4
Output: 5
Explanation: 5 tilings of 2×4.

Input: 0
Output: 1
Explanation: Empty floor: 1 way.

Constraints

• 0 <= n <= 10000

Asked by