U172624 博物馆记忆之树（memory）

因受到谣言的蛊惑，你和环彩羽来到了记忆博物馆。 博物馆里有一个$n$点无根树$T$，点的标号是$1\sim n$。同时给定非负整数$L$。 现在由你来给树上的节点黑白染色。然后，对于树上的每条边$(u, v)$，如果你给$u, v$染的颜色不一样，那么这条边就会断开。于是得到一个森林$F$。 接下来，你将给森林$F$添加一些边，使其变成一颗树$G$。但由于一些技术问题，对于任何$u, v$，如果$(u, v)\in T$并且$(u, v)\notin F$（即原本存在的边$(u, v)$由于你的染色而断开了），那么你就不能添加$(u, v)$这条边。 最后，环彩羽使用魔法获得了$k$个记忆碎片。$k$等于$F$中直径最长的树的直径。直径定义为树上最长路径的长度；路径$(u, v)$的长度定义为从节点$u$走到$v$最少经过多少条边。 可是你一回家就忘了你的染色方式以及添边方式，只记得$T$以及$L$还有“$k \leq L$”这个条件。 请你求出在满足你的记忆中的条件下，$G$可能的形态个数。两个树$G_1, G_2$不同，当且仅当二者边集不同；两条边$(u_1, v_1), (u_2, v_2)$(不妨设$u_1

第$1$行$2$个整数$n, L$。 接下来$n-1$行，每行$2$个整数$u, v$，表示$T$中存在边$(u, v)$。

$1$个整数，表示在满足“环彩羽获得的记忆碎片的个数不超过$L$”这个条件的前提下，$G$可能的形态个数模$10^7+19$。

对于$100\%$的数据，$1\leq n\leq 1000000, 0\leq L\leq n -1$。对于全部测试点，保证不会出现必须处理“求$0$的逆元”的情况。 | 子任务 | 分值 | $n$ | $L$ | 特殊性质 | | -----: | ---- | ------------: | -------: | -------------------------: | | 1 | 15 | $\leq8$ | | | | 2 | 20 | $\leq15$ | | | | 3 | 15 | $\leq100$ | | | | 4 | 10 | $\leq2000$ | | | | 5 | 5 | $\leq1000000$ | $=0$ | | | 6 | 5 | $\leq1000000$ | $\leq10$ | | | 7 | 5 | $\leq1000000$ | $=n-1$ | | | 8 | 10 | $\leq1000000$ | | $\forall (i, i + 1) \in T$ | | 9 | 15 | $\leq1000000$ | | |