← Home
```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

const MOD int64 = 1000000007

func modpow(a, e int64) int64 {
	res := int64(1)
	a %= MOD
	for e > 0 {
		if e&1 == 1 {
			res = res * a % MOD
		}
		a = a * a % MOD
		e >>= 1
	}
	return res
}

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, k int
	fmt.Fscan(in, &n, &k)

	adj := make([][]int, n+1)
	for i := 0; i < n-1; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)
		adj[u] = append(adj[u], v)
		adj[v] = append(adj[v], u)
	}

	if k%2 == 1 {
		fmt.Println(1)
		return
	}

	m := k / 2

	fact := make([]int64, n+1)
	invFact := make([]int64, n+1)
	fact[0] = 1
	for i := 1; i <= n; i++ {
		fact[i] = fact[i-1] * int64(i) % MOD
	}
	invFact[n] = modpow(fact[n], MOD-2)
	for i := n; i >= 1; i-- {
		invFact[i-1] = invFact[i] * int64(i) % MOD
	}

	C := func(N, K int) int64 {
		if K < 0 || K > N {
			return 0
		}
		return fact[N] * invFact[K] % MOD * invFact[N-K] % MOD
	}

	parent := make([]int, n+1)
	order := make([]int, 0, n)
	stack := []int{1}
	parent[1] = 0

	for len(stack) > 0 {
		v := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		order = append(order, v)
		for _, u := range adj[v] {
			if u != parent[v] {
				parent[u] = v
				stack = append(stack, u)
			}
		}
	}

	size := make([]int, n+1)
	for i := n - 1; i >= 0; i-- {
		v := order[i]
		size[v] = 1
		for _, u := range adj[v] {
			if u != parent[v] {
				size[v] += size[u]
			}
		}
	}

	var sum int64 = 0
	for v := 2; v <= n; v++ {
		s := size[v]
		term := C(s, m) * C(n-s, m) % MOD
		sum = (sum + term) % MOD
	}

	total := C(n, k)
	ans := (total + sum) % MOD
	ans = ans * modpow(total, MOD-2) % MOD
	fmt.Println(ans)
}
```