MOD = 10**9 + 7

def expand(num, used_color, from = nil)
  @counter *= (K - used_color)
  @counter %= MOD
  next_list = @hen_hash[num] - [from]
  add = 1
  add = 0 if from.nil?
  next_list.size.times do |i|
    expand(next_list[i], 1 + add +  i, num)
  end
end

N, K = gets.chomp.split.map(&:to_i)
lines = readlines
hens = []
@hen_hash = Hash.new([])
lines.each do |line|
  a, b = line.chomp.split.map(&:to_i)
  hens << [a, b]
  @hen_hash[a] = @hen_hash[a] + [b]
  @hen_hash[b] = @hen_hash[b] + [a]
end

if @hen_hash.values.map(&:size).max + 1 > K
  puts 0
  exit
end

@counter = 1
expand(1, 0)

puts @counter

