require 'set'
N,K = gets.chomp.split(" ").map(&:to_i)
mat = readlines.map{|n| n.chomp.split(" ").map(&:to_i)}


@graph = Hash.new{[]}
mat.each do |n|
    arr = @graph[n[0]]
    arr << n[1]
    @graph[n[0]] = arr
    arr = @graph[n[1]]
    arr << n[0]
    @graph[n[1]] = arr
end

def log(n)
    #p n
end
# p graph
# p @graph[1]
def perms(n, k)
    return 1 if n == 0 or k == 0
    log ["args",n,k]
    ret = (1..n).inject(1,:*) / (1..(n-k)).inject(1,:*)
    log ["perms", ret]
    ret
end

@q = []
@visited = Set.new
@color_nums = [] #nodes color number
log [N,K]
log @graph
def dfs(v, minus)
    if minus != -2
        minus -= 1
    end
    @visited.add(v)
    log [v,minus]
    children = Set.new(@graph[v])-@visited
    @color_nums << perms(K + minus, children.size)
    log ["color_nums",@color_nums]
    arr = @graph[v]
    arr.each do |n|
        if not @visited.include? n
            dfs(n,minus)
        end
    end
end
dfs(1,0)
puts K * @color_nums.reduce(1, :*) % 1000000007
