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: _input = [i for i in open(0).read().split("\n") if i]
  n, k = [int(i) for i in _input[0].split()]
  edge = tuple([tuple([int(p) for p in i.split()]) for i in _input[1:n]])
  
  factorial = [0] * (k + 1)
  inverse = [0] * (k + 1)
  MOD = 1000000007
  
  
  # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/175024
  def mod_pow1(n, k, mod):
      a = 1
      while k:
          if (k & 1) == 1:
              a = (a * n) % mod
          n = (n * n) % mod
          k >>= 1
      return a
  
  
  # Ref: https://www.smartbowwow.com/2018/10/mod1097.html
  def mod_pow2(n, k, mod):
      if k == 0:
          return 1
      if k % 2 == 0:
          a = mod_pow2(n, k // 2, mod)
          return (a * a) % mod
      else:
          return (n * mod_pow2(n, k - 1, mod)) % mod
  
  
  mod_pow = pow
  
  
  def mod_factorial_inverse(k, mod):
      factorial[0] = 1
      inverse[0] = 1
  
      # Ref: http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
      for i in range(1, k + 1):
          factorial[i] = (i * factorial[i - 1]) % mod  # factrial[i]
          inverse[i] = mod_pow(factorial[i], mod - 2, mod)  # inverse[i]
  
  
  if not edge:
      print(k)
  else:
      all_edge = tuple([[] for _ in range(n + 1)])
      for e in edge:
          all_edge[e[0]].append(e[1])
          all_edge[e[1]].append(e[0])
  
      if [v for v in all_edge if len(v) >= k]:
          print(0)
      else:
          mod_factorial_inverse(k, 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"}]