output_description: Print the number of ways to have H blocks on every square, modulo 10^9+7.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N H D
attempt: n, h, d = map(int, input().split())
  MOD = 10**9 + 7
  
  # dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
  dp = [[0] * (n + 1) for i in range(h + 1)]
  dp[0][n] = 1
  
  # O(HDN)
  for i in range(h):
      # j = 0 -> j = 1 にする
      for diff in range(1, d + 1):
          if i + 1 - diff < 0:
              continue
          for cnt in range(1, n + 1):
              dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
              dp[i + 1][1] %= MOD
  
      # j -> j + 1 にする
      for j in range(2, n + 1):
          dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
          dp[i + 1][j] %= MOD
  
  print(dp[-1][-1])
  
problem_description: Statement
  
  There are N squares arranged in a row, numbered 1 to N from left to right.
  Takahashi will stack building blocks on these squares, on which there are no
  blocks yet.
  
  He wants to stack blocks on the squares evenly, so he will repeat the
  following operation until there are H blocks on every square:
  
    * Let M and m be the maximum and minimum numbers of blocks currently stacked on a square, respectively. Choose a square on which m blocks are stacked (if there are multiple such squares, choose any one of them), and add a positive number of blocks on that square so that there will be at least M and at most M + D blocks on that square.
  
  Tell him how many ways there are to have H blocks on every square by repeating
  this operation. Since there can be extremely many ways, print the number
  modulo 10^9+7.
samples: [{"input": "2 2 1", "output": "6\n    \n\nThe possible transitions of (the number of blocks on Square 1, the number of\nblocks on Square 2) are as follows:\n\n  * (0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2)\n\n  * (0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2)\n\n  * (0, 0) -> (0, 1) -> (2, 1) -> (2, 2)\n\n  * (0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2)\n\n  * (0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2)\n\n  * (0, 0) -> (1, 0) -> (1, 2) -> (2, 2)\n\nThus, there are six ways to have two blocks on every square.\n\n* * *"}, {"input": "2 30 15", "output": "94182806\n    \n\n* * *"}, {"input": "31415 9265 3589", "output": "312069529\n    \n\nBe sure to print the number modulo 10^9+7."}]