def legoBlocks(n, m):

    # Step 1: O(W)       
    ## Four base cases (widths 0-3) for row walls
    row_combinations = [1, 1, 2, 4]
    
    # Build row combinations up to current wall's width
    while len(row_combinations) <= m: 
        row_combinations.append(sum(row_combinations[-4:]))
    
    # Compute total combinations 
    # for constructing a wall of height N of varying widths
    total = [pow(c, n) for c in row_combinations]
    
    # Step 3: O(W^2)
    # Find the number of unstable wall configurations 
    # for a wall of height N of varying widths
    unstable = [0, 0]
    
    # Divide the wall into left part and right part,
    # and calculate the combination of left part and right part.
    # From width is 2, we start to consider about violations
    for i in range(2, m + 1):
        # i: current total width, j: left width, i - j: right width
        # f: (left part - previous vertical violation)*right part
				# result = sum of f applied to all 1-i
				
        f = lambda j: (total[j] - unstable[j]) * total[i - j]
        result = sum(map(f, range(1, i)))
        unstable.append(result)
    
    return (total[m] - unstable[m])