给你一棵由 $$$n$$$ 节点组成的树。您应该用满足以下条件的整数来标记其每个 $$$n-1$$$ 边:
- 每个整数必须大于 $$$0$$$;
- 所有 $$$n-1$$$ 数字的乘积应等于 $$$k$$$;
- 所有 $$$n-1$$$ 整数中 $$$1$$$-s 的数量必须尽可能小。
让我们将 $$$f(u,v)$$$ 定义为从节点 $$$u$$$ 到节点 $$$v$$$ 的简单路径上的数字之和。另外,令 $$$\sum\limits_{i=1}^{n-1} \sum\limits_{j=i+1}^n f(i,j)$$$ 为树的分布索引。
找到你可以获得的最大可能的分布指数。由于答案可能太大,请以 $$$10^9 + 7$$$ 为模打印它。
在这个问题中,由于数字 $$$k$$$ 可能很大,因此给出 $$$k$$$ 素因数分解的结果。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$) — 树中的节点数。
接下来的 $$$n-1$$$ 行描述一条边:第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$; $$$u_i \ne v_i$$$) — 由第 $$$i$$$ 条边。
下一行包含一个整数 $$$m$$$ ($$$1 \le m \le 6 \cdot 10^4$$$) — $$$k$$$ 的质因数数量。
下一行包含 $$$m$$$ 质数 $$$p_1, p_2, \ldots, p_m$$$ ($$$2 \le p_i < 6 \cdot 10^4$$$) 使得 $$$k = p_1 \cdot p_2 \cdot \ldots \cdot p_m$$$。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$,所有测试用例的$$$m$$$总和不超过$$$6 \cdot 10^4$$$,并且每个测试用例的给定边形成一棵树。
输出
打印您可以获得的最大分布指数。由于答案可能太大,请以 $$$10^9+7$$$ 为模打印它。
示例
输入 #1
3 4 1 2 2 3 3 4 2 2 2 4 3 4 1 3 3 2 2 3 2 7 6 1 2 3 4 6 7 3 5 1 3 6 4 7 5 13 3
输出 #1
17 18 286
注意
在第一个测试用例中,最佳方法之一是下图:
在这种情况下,$$$f(1,2)=1$$$,$$$f(1,3)=3$$$,$$$f(1,4)=5$$$,$$$f(2,3)=2$$$,$$$f(2,4)=4$$$,$$$f(3,4)=2$$$,所以这些$$$6$$$的总和数字是$$$17$$$。
在第二个测试用例中,最佳方法之一如下图所示:
在这种情况下,$$$f(1,2)=3$$$、$$$f(1,3)=1$$$、$$$f(1,4)=4$$$、$$$f(2,3)=2$$$、$$$f(2,4)=5$$$、$$$f(3,4)=3$$$,所以这些$$$6$$$的总和数字是$$$18$$$。