Domino and Tromino Tiling
You have two types of tiles: a 2 x 1 domino shape and a tromino shape. You may rotate these shapes.
Given an integer n, return the number of ways to tile a 2 x n board. Since the answer may be very large, return it modulo 10^9 + 7.
In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by the same tile.
Examples
Input: 3
Output: 5
Input: 1
Output: 1
Hints
Consider the base cases for small values of `n` (like `n = 1`, `n = 2`, `n = 3`) and derive a recurrence relation by analyzing how the board can be filled incrementally.
Think about the different ways to fill the last column(s) of the `2 x n` board, considering both dominoes and trominoes, and how these choices affect the remaining subproblems.
Model the problem using dynamic programming with states representing the possible configurations of the last column(s) (e.g., fully filled, partially filled with a tromino, etc.), and derive a recurrence that accounts for all valid transitions between these states.
Domino and Tromino Tiling
You have two types of tiles: a `2 x 1` domino shape and a tromino shape. You may rotate these shapes.