Tile 2xn board
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) -> intExample 1
Input
num_tilings(3)Output
5