output_description: Print an integer representing the minimum total travel expense.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N A B
attempt: import sys
  
  sys.setrecursionlimit(10**6)
  
  
  def perm(n, k):
      return fact[n] * ifact[n - k] % mod
  
  
  def dfs(v, p):
      global ans
      for nv in link[v]:
          if nv == p:
              continue
          dfs(nv, v)
      # p = -1の時は根である。根も含めて塗り分け方を考えるので、
      # n = K、c = 子の数+根の数で塗り分け方を求める
      # 見るのが子の時はその上の頂点とその親が塗られているので、
      # n = K-2、c = 子の数となる
      if p == -1:
          n = K
      else:
          n = K - 2
      if p == -1:
          k = len(link[v]) + 1
      else:
          k = len(link[v]) - 1
  
      ans *= perm(n, k)
      ans %= mod
  
  
  N, K = map(int, input().split())
  link = [[] for _ in range(N)]
  for i in range(N - 1):
      a, b = map(int, input().split())
      link[a - 1].append(b - 1)
      link[b - 1].append(a - 1)
  
  mod = 10**9 + 7
  ans = 1
  
  fact = [0] * (10**5 + 1)
  fact[0] = 1
  fact[1] = 1
  for i in range(2, 10**5 + 1):
      fact[i] = fact[i - 1] * i
      fact[i] %= mod
  ifact = [0] * (10**5 + 1)
  for i in range(10**5 + 1):
      ifact[i] = pow(fact[i], mod - 2, mod)
      ifact[i] %= mod
  
  dfs(0, -1)
  
  print(ans % mod)
  
problem_description: Statement
  
  N of us are going on a trip, by train or taxi.
  
  The train will cost each of us A yen (the currency of Japan).
  
  The taxi will cost us a total of B yen.
  
  How much is our minimum total travel expense?
samples: [{"input": "4 2 9", "output": "8\n    \n\nThe train will cost us 4 \\times 2 = 8 yen, and the taxi will cost us 9 yen, so\nthe minimum total travel expense is 8 yen.\n\n* * *"}, {"input": "4 2 7", "output": "7\n    \n\n* * *"}, {"input": "4 2 8", "output": "8"}]