MOD = 10**9 + 7

def expand(num, used_color, from = nil)
  @counter = @counter * (K - used_color) % MOD
  next_list = @hen_hash[num] - [from]
  add = 1
  add = 0 if from.nil?
  next_list.size.times do |i|
    @expand_list << [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_list  = [[1, 0, nil]]

until @expand_list.empty?
  fact = @expand_list.shift
  expand(fact[0], fact[1], fact[2])
end

puts @counter

