Counting Tilings - Implementation

Precompute transitions, then run DP:

function countTilings(n, m):
    MOD := 1000000007
    trans := array of size 2^n, each entry is empty list
    
    function fill:
        if row = n then trans[cur_mask].append(next_mask)
        return
        if cur_mask has bit row set then fill
        else fill
        if row + 1 < n and cur_mask bit (row+1) not set then fill
    
    for mask from 0 to 2^n - 1:
        fill(0, mask, 0)
    
    dp := 2D (two-dimensional) array (m+1) x 2^n, all zeros
    dp[0][0] := 1
    for c from 0 to m - 1:
        for cur_mask from 0 to 2^n - 1:
            Each next_mask in trans[cur_mask]:
                dp[c+1][next_mask] := mod MOD
    return dp[m][0]

Time: $O(m \cdot 2^n \cdot T)$. Space: $O(2^n)$ for the profile states.