给定一棵有 $n$ 个顶点的有根树，其中 $r$ 是树的根。每个顶点 $x$ 都有一个权值 $a_x$。

我们定义从 $x$ 开始寻找 $y$ 的 DFS 过程如下：

1. 将 $x$ 入栈。
2. 查看栈顶元素 $w$。如果 $w = y$，过程结束。否则，如果 $w$ 至少有一个未被访问的儿子，则等概率选择其中一个儿子并将其入栈。
3. 重复步骤 2，直到没有未被访问的儿子。
4. 将栈顶元素出栈。
5. 重复步骤 2，直到栈为空。

该过程合法当且仅当 $y$ 在 $x$ 的子树中。

定义 $f(x, y)$ 为从 $x$ 开始寻找 $y$ 的 DFS 过程中，所有被推入栈中的顶点的权值的最小值的期望。

现在我们想要计算所有合法对 $(x, y)$ 的 $\sum f(x, y)$。可以证明答案可以表示为一个不可约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 是整数且 $y \not\equiv 0 \pmod{998\,244\,353}$。 输出等于 $x \cdot y^{-1} \pmod{998\,244\,353}$ 的整数。换句话说，输出一个整数 $a$，使得 $0 \le a < 998\,244\,353$ 且 $a \cdot y \equiv x \pmod{998\,244\,353}$。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ 和 $r$ ($1 \le n \le 4 \cdot 10^5, 1 \le r \le n$)，分别表示树的顶点数和根。

接下来一行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ ($1 \le a_i \le 10^9$) 表示顶点 $i$ 的权值。

接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示树的一条边。

保证 $\sum n \le 8 \cdot 10^5$。同时保证给定的图确实是一棵树。

输出格式

输出 $T$ 行。每行必须包含一个整数：对应测试用例的答案。

样例

样例输入 1

4
1 1
1
3 3
3 3 4
3 1
3 2
6 1
5 2 4 1 3 6
1 2
1 6
2 3
2 4
4 5
5 1
5 4 3 2 1
1 2
1 3
3 4
3 5

样例输出 1

1
16
34
499122202