output_description: Print the number of the sequences that contain an X,Y,Z-Haiku, modulo 10^9+7.
  
  * * *
input_description: The input is given from Standard Input in the following format:
  
      
      
      N X Y Z
attempt: n, x, y, z = map(int, input().split())
  mod = 10**9 + 7
  
  
  def judge(s):
      sx = 0
      px = -1
      for i in range(len(s) - 1, -1, -1):
          sx += int(s[i])
          if sx == x:
              px = i
              break
      if px == -1:
          return True
  
      sy = 0
      py = -1
      for i in range(px - 1, -1, -1):
          sy += int(s[i])
          if sy == y:
              py = i
              break
      if py == -1:
          return True
  
      sz = 0
      for i in range(py - 1, -1, -1):
          sz += int(s[i])
          if sz == z:
              return False
      return True
  
  
  d = [{}, {"": 1}]
  sample = ("1", "2", "3", "4", "5", "6", "7", "8")
  
  for i in range(n):
      d[i % 2] = {}
      for plus in sample:
          for e in d[(i + 1) % 2]:
              if judge(e + plus):
  
                  a = e + plus
                  s = 0
                  for elt in a:
                      s += int(elt)
                  ind = 0
                  while s >= x + y + z:
                      s -= int(a[ind])
                      ind += 1
  
                  ind2 = -1
                  for j in range(len(a) - 1, ind - 1, -1):
                      if int(a[j]) > z:
                          ind2 = j
                          break
                  new = a[max(ind, ind2) :]
  
                  pl = d[(i + 1) % 2][e]
                  if plus == "8":
                      pl = pl * 3 % mod
                  if new in d[i % 2]:
                      d[i % 2][new] = (d[i % 2][new] + pl) % mod
                  else:
                      d[i % 2][new] = pl
  
  res = 0
  for e in d[(n + 1) % 2].values():
      res = (res + e) % mod
  print((pow(10, n, mod) - res) % mod)
  
problem_description: Statement
  
   _Haiku is a short form of Japanese poetry. A Haiku consists of three phrases
  with 5, 7 and 5 syllables, in this order._
  
  Iroha is looking for _X,Y,Z -Haiku_ (defined below) in integer sequences.
  
  Consider all integer sequences of length N whose elements are between 1 and
  10, inclusive. Out of those 10^N sequences, how many contain an X,Y,Z-Haiku?
  
  Here, an integer sequence a_0, a_1, ..., a_{N-1} is said to _contain an
  X,Y,Z-Haiku_ if and only if there exist four indices x, y, z, w (0 ≦ x < y < z
  < w ≦ N) such that all of the following are satisfied:
  
    * a_x + a_{x+1} + ... + a_{y-1} = X
    * a_y + a_{y+1} + ... + a_{z-1} = Y
    * a_z + a_{z+1} + ... + a_{w-1} = Z
  
  Since the answer can be extremely large, print the number modulo 10^9+7.
samples: [{"input": "3 5 7 5", "output": "1\n    \n\nHere, the only sequence that contains a 5,7,5-Haiku is [5, 7, 5].\n\n* * *"}, {"input": "4 5 7 5", "output": "34\n    \n\n* * *"}, {"input": "37 4 2 3", "output": "863912418\n    \n\n* * *"}, {"input": "40 5 7 5", "output": "562805100"}]