For a tiling puzzle in the textbook, Oindrila must count the number of ways to fully tile a 2×N board using only 1×2 dominoes. Given N, print the number of ways to completely tile a 2×N board using 1×2 (or 2×1) dominoes, modulo 10^9+7. (This reduces to a Fibonacci-like recurrence — derive it yourself rather than assuming the answer.)
Input
One integer N.
Output
Number of tilings mod (10^9+7).
Constraints
1 ≤ N ≤ 10^6
Sample Input
3
Sample Output
3
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.