题目描述 树是一种具有 个点 条边的无向连通图。

六一儿童节快到了，老师安排你去给一棵树进行装饰，从而让其变得更好看。老师给了你 桶染料，每一种染料的颜色都不同。你需要将这棵树染色之后尽量显得不单调，具体来说：

对于树上任意两个距离不超过 的节点 和 ，其所染的颜色不相同。 你想要知道：一共有多少种染色方法，可以使得这棵树满足上述条件？不一定每一种颜料都需要使用。由于答案可能会很大，请输出答案对 取模之后的结果。

输入格式 第一行两个正整数 ，分别表示树的节点个数和染色颜料种数。

接下来 行，每行两个正整数 ，表示树上节点 和 之间有一条边。保证输入给出的是一棵树。

输出格式 输出一行一个整数，表示染色方案数，对 取模后的结果。