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(100000)
  
  N, K = list(map(int, input().split()))
  ab = []
  for i in range(N - 1):
      ab.append(list(map(int, input().split())))
  
  ki = []
  
  for i in range(N):
      ki.append(dict())
      ki[-1]["eda"] = []
  
  for i in range(N - 1):
      ki[ab[i][0] - 1]["eda"].append([ab[i][0] - 1, ab[i][1] - 1])
      ki[ab[i][1] - 1]["eda"].append([ab[i][1] - 1, ab[i][0] - 1])
  
  
  def P(m, n):
      if m <= 0 or n <= 0:
          return 0
      else:
          num = 1
          for i in range(n):
              num *= m - i
          return num
  
  
  def saiki(i, base, ki):
      num = 1
      eda_num = len(ki[i]["eda"]) - 1
      if eda_num == 0:
          return num
      num *= P(K - 2, eda_num)
  
      for edge in ki[i]["eda"]:
          if edge[1] != base:
              num *= saiki(edge[1], i, ki)
              num = num % 1000000007
              # print(num)
  
      return num
  
  
  total_num = K
  if len(ki[0]["eda"]) != 0:
      total_num *= P(K - 1, len(ki[0]["eda"]))
      for edge in ki[0]["eda"]:
          total_num *= saiki(edge[1], 0, ki)
          total_num = total_num % 1000000007
          if total_num == 0:
              break
  
  print(total_num)
  
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"}]