Profile DP (DP on Broken Profile)

// Count ways to tile n×m grid with 1×2 dominoes
// Process cells column by column, state = which cells in column are "pre-filled"
function countDominoTilings(n, m) {
    const MOD = 1e9 + 7;
    // dp[mask] = ways to reach this column with mask indicating pre-filled cells
    let dp = new Array(1 << n).fill(0);
    dp[0] = 1; // start: no cells pre-filled in first column

    for (let col = 0; col < m; col++) {
        // For each column, process rows top to bottom
        // Use DFS/recursion to enumerate valid placements
        const ndp = new Array(1 << n).fill(0);
        function dfs(row, prevMask, curMask) {
            if (row === n) { ndp[curMask] += dp[prevMask]; return; }
            const filled = (prevMask >> row) & 1;
            if (filled) {
                // This cell is already filled by a horizontal domino from previous column
                dfs(row + 1, prevMask, curMask);
            } else {
                // Option 1: place horizontal domino extending to next column
                dfs(row + 1, prevMask, curMask | (1 << row));
                // Option 2: place vertical domino (needs row+1 to also be empty)
                if (row + 1 < n && !((prevMask >> (row + 1)) & 1)) {
                    dfs(row + 2, prevMask, curMask);
                }
            }
        }
        for (let mask = 0; mask < (1 << n); mask++) {
            if (dp[mask]) dfs(0, mask, 0);
        }
        dp = ndp.map(v => v % MOD);
    }
    return dp[0]; // all cells filled, no cells pre-filled for next column
}