Tile 2xn board

Write codeMedium25 min

Your task

You have an unlimited supply of 2x1 dominoes and L-shaped trominoes (a tromino covers three cells in an L). Count the number of ways to fully tile a 2 x n board; two tilings are different if some cell is covered by a different shape. Because the count grows fast, return the answer modulo 1_000_000_007. Assume 0 <= n <= 1000.

Examples

num_tilings(n: int) -> int
Example 1
Inputnum_tilings(3)
Output5