790. Domino and Tromino Tiling - LeetCode Solution

class Solution:
    def numTilings(self, n: int) -> int:
        md = 10**9 + 7
        dp = [0] * 10001
        dp[1] = 1
        dp[2] = 2
        dp[3] = 5
        if n<=3:
            return dp[n]
        for i in range(4, n+1, 1):
            dp[i] = 2*dp[i-1] + dp[i-3]
            dp[i]%=md
        return dp[n]