Migrated from Lutece 3226 树上序列

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

给定一棵 $n$ 个点且以 $1$ 为根的有根树，及常数 $V$。

求序列 $\{a_n\}$ 的个数，满足

1. $\forall i\in[1,n], a_i\in[1,V]$
2. $\forall i\in[2,n],a_i\leq a_{fa_i}$

其中 $fa_i$ 表示节点 $i$ 的父节点。答案对 $10^9+7$ 取模。

Input

第一行，两个正整数 $n$ 和 $V$。

接下来 $n-1$ 行，每行两个正整数，描述一条边 $u\leftrightarrow v$ 。

Output

一行，一个整数，表示答案。

Samples

4 3
2 1
3 1
4 1

36

Constraints

$1\leq n\leq 5\times 10^3$，$1\leq V\leq 10^9$

Resources

2024 UESTC ICPC Training for Math