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 an 2 x n board. Since the answer may be very large, return it modulo 109 + 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 a tile.

&nbsp;
Example 1:

Input: n = 3
Output: 5
Explanation: The five different ways are show above.


Example 2:

Input: n = 1
Output: 1


&nbsp;
Constraints:


	1 &lt;= n &lt;= 1000


class Solution(object):
    def numTilings(self, n):
        dp = [1, 2, 5] + [0] * n
        for i in range(3, n):
            dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % 1000000007
        return dp[n - 1]
class Solution {
    public int numTilings(int n) {
        long[] dp = new long[n + 3]; dp[0] = 1; dp[1] = 2; dp[2] = 5;
        for (int i = 3; i < n; i ++) {
            dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % 1000000007;
        }
        return (int)dp[n - 1];
    }
}
class Solution {
public:
    int numTilings(int n) {
        long dp[n+1];
        dp[0]=1;
        for(int i=1; i<=n; i++){
            if(i<3)
                dp[i]=i;
            else
                dp[i] = (dp[i-1]*2+dp[i-3])%1000000007;
        }
        return (int)dp[n];
    }
};
var numTilings = function(n) {
    let mod = 10 ** 9 + 7;
    let len = 4;
    let ways = new Array(len).fill(0);

    // base cases
    ways[0] = 1;
    ways[1] = 1;
    ways[2] = 2;

    // already calculated above
    if (n < len - 1) {
        return ways[n];
    }

    // use % len to circulate values inside our array
    for (var i = len - 1; i <= n;i++) {
        ways[i % len] = (
            ways[(len + i - 1) % len] * 2
            +
            ways[(len + i - 3) % len]
        ) % mod;
    }

    return ways[(i - 1) % len];
};
Domino and Tromino Tiling