def legoBlocks(n, m):
    # If only one column or one row, there's only one way to build the wall
    if m == 1:
        return 1
    if n == 1:
        return 1 if 1 <= m <= 4 else 0
        
    MOD = pow(10, 9) + 7
    
    # Number of layouts to build a 1 x k wall for k = 1 to m
    p = [0, 1, 2, 4, 8]  # Base cases for widths 1 to 4
    for k in range(5, m + 1):
        # For width k, sum the previous four widths
        p.append(sum(p[-i] % MOD for i in range(1, 5)))
    
    # Number of layouts to build an n x k wall for k = 1 to m
    p = [pow(val, n, MOD) for val in p]
    
    # Number of good layouts (without any complete row gaps) to build n x k wall for k = 1 to m
    g = [0, 1]
    for k in range(2, m + 1):
        # Calculate the number of bad layouts for width k
        bad_layouts_num = sum(g[j] * p[k - j] for j in range(1, k)) % MOD
        # Explanation:
        # g[j] * p[k - j] represents the number of ways to build an n x k wall with a vertical division
        # at position j, resulting in a good layout on the left (g[j]) and any layout on the right (p[k - j]).
        # Summing these products for all j from 1 to k-1 gives the total number of bad layouts where there
        # is at least one complete vertical division in the wall.
        
        # Subtract bad layouts from total layouts to get good layouts
        g.append((p[k] - bad_layouts_num) % MOD)
    
    return g[m]

/**
 * Raise a num to an exponent and mod the result
 * NOTE: don't use Math.pow() since it will give
 * incorrect results since it does not mod the
 * intermediate results
 */
private static long pow(long num, int exp, long mod) {
    long res = num;
    while (exp-- > 1) {
        res = (res * num) % mod;
    }

    return res;
}

/**
 * Strategy using Dynamic Programming:
 * 1. Create an array where each index represents the width
 * and store the number of permuations for a single row.
 * 
 * 2. Create an array where each index represents the width
 * and store the number of valid and invalid permutations for
 * the total number of rows (height)
 * 
 * 3. Create an array where each index represents the width
 * and store the number of invalid permuations of each
 * total number of rows.
 * 
 * 4. The final result will be the substracion of (2) - (3):
 * result = (valid + invalid) - (invalid)
 * 
 */
public static int legoBlocks(int h, int w) {
    long divisor = 1000000007; // every calculation must be mod by this number

    // STEP 1:
    // Permutations for a single row is:
    // when width=0; 0 valid permutation
    // when width=1; 1 valid permutation
    // when width=2; 2 valid permutations
    // when width=3; 4 valid permutations
    // when width=4; 8 valid permutations
    // when widht=N; the sum of the previous 4 widths: (N-1) + (N-2) + (N-3) + (N-4)
    List<Long> singleRow = new ArrayList<>(Arrays.asList(0L, 1L, 2L, 4L, 8L));

    // STEP 2:
    // Total permutations for all rows:
    // when width=0; singleRow[0]^h valid permutations (always 0)
    // when width=1; singleRow[1]^h valid permutations (always 1)
    // when width=2; singleRow[2]^h valid permutations
    // when width=3; singleRow[3]^h valid permutations
    // when width=4; singleRow[4]^h valid permutations
    // when width=N; singleRow[N]^h valid permutations
    List<Long> total = new ArrayList<>(
            Arrays.asList(0L, 1L,
                    pow(2, h, divisor),
                    pow(4, h, divisor),
                    pow(8, h, divisor)));

    // Completes the singleRow and total arrays dynamically from
    // the previous values according to the above rules
    for (int i = 5; i <= w; i++) {
        long val = (singleRow.get(i - 1) + singleRow.get(i - 2) +
                singleRow.get(i - 3) + singleRow.get(i - 4)) % divisor;
        singleRow.add(val);

        total.add(pow(val, h, divisor));
    }

    // STEP 3 Invalid permutations:
    // Perform a vertical cut across all rows of bricks
    // when width=0; 0 invalid permutations
    // when width=1; 0 invalid permutations
    List<Long> invalid = new ArrayList<>(Arrays.asList(0L, 0L));

    // This is the tricky part:
    // Starting with a 2-width cut up to the width
    // For each cut, walk 1-width at a time up to the cut
    // and add the result of the left * right (invalid permutations)
    // the left part are the valid permutations
    // the right part are all possible permutations (valid and invalid)
    for (int cut = 2; cut <= w; cut++) {
        long anum = 0;
        for (int i = 1; i < cut; i++) {
            long l = total.get(i) - invalid.get(i);
            long r = total.get(cut - i);
            anum += ((l * r) % divisor);
        }
        invalid.add(anum % divisor);
    }

    // STEP 4
    // We have finally calculated all the valid and invalid permuations
    // we only substract the total permutations from the invalid permuations 
    long r = (total.get(w) - invalid.get(w)) % divisor;

    // In case the substraction is negative
    // add the divisor(mod) to the result to find out the real value
    while (r < 0)
        r += divisor;

    return (int) r;
}

function legoBlocks(n, m) {
    // Write your code here
    const A = 1000000007n;
    const r = new Array(m+1).fill(0n);
    const a = new Array(m+1).fill(0n);
    
    a[0] = 1n;
    for (let j = 1; j <= m; j++) {
        a[j] += (j-1>=0) ? a[j-1] : 0n;
        a[j] += (j-2>=0) ? a[j-2] : 0n;
        a[j] += (j-3>=0) ? a[j-3] : 0n;
        a[j] += (j-4>=0) ? a[j-4] : 0n;
    }
    
    for (let j = 1; j <= m; j++) {
        const n1 = a[j] % A;
        const sum = n1 ** BigInt(n);
        a[j] = sum % A;
    }
    
    r[1] = 1n;
    for (let j = 2; j <= m; j++) {
        r[j] = a[j];
        for (let k = 1; k < j; k++) {
            const n1 = r[k] * a[j-k];
            r[j] -= n1;
        }
        // ATTENTION! in javascript, when the left operand of bigint is negative
        // need to add  +A to be positive, different from python for example
        r[j] = r[j] % A + A; 
    }

    return r[m] % A;
}