A corridor floor is a grid of 2 rows and n columns. You have an unlimited supply of 1 x 2 tiles that may be laid vertically (filling one column) or horizontally (a pair of them fills two columns). Return the number of distinct ways to cover the whole floor, modulo 10**9 + 7. An empty corridor (n = 0) has exactly one tiling.
Examples
Input: n = 4
Output: 5
Explanation: writing V for a vertical tile and HH for a stacked horizontal pair,
the five tilings are V V V V, V V HH, V HH V, HH V V, HH HH.
Input: n = 1
Output: 1
Constraints
0 <= n <= 10**5- Target complexity: O(n) time.
Goals
- Count tilings by looking at what covers the last column
- Apply a modulus at every addition so numbers stay small