题目描述

歪歪有一个大院子，里面种满了魔法树。

魔法树是由 \(n\) 个节点， \(n-1\) 条边构成的联通图，它的根节点是 \(1\) 号点，其中每个点都有自己的魔法属性 \(a_i\)。每棵魔法树神奇的一点就是结点与结点之间的魔法属性会相互作用，即当魔法树上三个不同的节点 \(i, j, k\) 满足： \(LCA_{i, j} = LCA_{i, k} = LCA_{j, k}\) 时，他们就会激发出 \(a_i \times a_j \times a_k\) 的魔法值，而魔法树的总魔法值即是所有满足条件的三个节点所激发出的魔法值总和 \(\sum\limits_{i < j < k}^{} a_{i} a_{j} a_{k}\)。当然，也有可能魔法树上找不到满足条件的三个节点，那它的魔法值即为 \(0\)。

现在歪歪的院子里有 \(T\) 棵魔法树，她想知道每棵魔法树的总魔法值是多少，但是她忙着种其它的魔法树，所以你来告诉她吧。总魔法值可能很大，你告诉她对 \(998244353\) 取模之后的值吧。

注： \(LCA_{i, j}\) 表示 \(i\) 和 \(j\) 的树上最近公共祖先。

本题输入量较大，建议用 std::ios::sync_with_stdio(false) 关同步流然后用 cin 读入，不建议用 scanf 或较慢的快读，HDOJ 的 scanf 速度极慢。

输入格式

第一行输入歪歪种的魔法树棵数 \(T\)。

对于每一棵树，先输入一个正整数 \(n\)，表示这棵魔法树的节点个数。

接下来 \(n-1\) 行，每行输入两个正整数 \(u, v\)，表示节点 \(u\) 与节点 \(v\) 之间有一条边。

接下来一行，输入 \(n\) 个正整数，第 \(i\) 个正整数为 \(a_i\)，表示第 \(i\) 号节点的魔法属性为 \(a_i\)。

数据保证： \(T \le 40\)， \(1 \le n \le 10^5\)， \(1 \le u, v \le n\)， \(1 \le a_i \le 10^9\)，保证输入的是一棵树。

输出格式

输出 \(T\) 行。

第 \(i\) 行表示歪歪的第 \(i\) 棵魔法树的魔法值。结果对 \(998244353\) 取模。

样例输入

3
7
1 2
2 3
1 4
1 5
4 6
1 7
1 1 1 3 2 3 2
5
1 2
1 3
1 4
2 5
1 2 5 1 3
6
1 2
1 3
2 4
2 5
1 6
9 6 8 1 10 8

样例输出

128
60
4172