def legoBlocks(n, m):
  modulo = 10 ** 9 + 7
  # calculate num_permutations for one line
	# base cases:
	# (1, 1): (1,)
	# (1, 2): ((1, 1), (2,))
	# (1, 3): ((1, 1, 1), (1, 2), (2, 1), (3,))
	# (1, 4): ((1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1), (2, 2), (1, 3), (3, 1), (4,))
  num_permutations = [0, 1, 2, 4, 8]
  # iterate out further with dynamic programming expanding on prior subproblems:
  # each iteration, include 1-width block after all the i-1-width ways,
  # plus 2-width block after all the i-2-width ways, etc. up to the 4-width block
  for i in range(5, m+1):
    num_permutations.append((num_permutations[i - 1] + num_permutations[i - 2] + num_permutations[i - 3] + num_permutations[i - 4]) % modulo)
  
  num_permutations_for_n = [((i ** n) % modulo) for i in num_permutations]
  # intuitively, 0 ways to make a width-0 "good" wall, and only 1 way to make a width-1 "good" wall
  good_permutations = [0, 1]
  # any "good" wall permutation of width < w is essentially one of the "invalid" left portions of a "bad" wall, so we subtract those out, multiplied by the permutations_for_n 
  for i in range(2, m+1):
    gp_for_i = num_permutations_for_n[i]
    for j in range(1, i):
      gp_for_i -= (good_permutations[j] * num_permutations_for_n[i-j])
    good_permutations.append(gp_for_i % modulo)
  return good_permutations[m]