今天，Rikka 正在玩一个策略游戏。她已经完成了游戏的第一阶段：她已经建立了自己的国家。

Rikka 拥有 $n$ 座城市，由 $n-1$ 条双向道路连接。任意两座城市之间都可以通过道路到达。Rikka 决定将这些城市奖励给 $n$ 位忠诚的将军。这些将军根据贡献大小被标记为 $1$ 到 $n$。最初，Rikka 决定将第 $i$ 座城市奖励给第 $p_i$ 位将军，其中 $p_1, p_2, \dots, p_n$ 是一个长度为 $n$ 的排列。

随后，Rikka 召集了所有将军并向他们展示了初步方案。将军们可以在满足以下两个限制的情况下交换他们的城市。持有城市 $a$ 的将军 $u$ 可以与持有城市 $b$ 的将军 $v$ 交换城市，当且仅当：

• 将军 $u$ 和将军 $v$ 的贡献相近，即 $|u - v| = 1$；
• 城市 $a$ 和城市 $b$ 的地理位置相近，即城市 $a$ 和城市 $b$ 之间存在一条道路。

在交换过程中，一位将军可以多次更换他/她的城市，同时，一座城市也可以在多位将军之间交换。

不出所料，将军们之间爆发了争吵。看来确定城市的所有权需要很长时间。所有这些事情让 Rikka 感到厌烦。为了找点乐子，Rikka 希望你计算出可能的奖励方案数量。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2 \times 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示城市的数量。

接下来 $n-1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示城市 $u$ 和城市 $v$ 之间的一条道路。

最后一行包含 $n$ 个整数 $p_i$ ($1 \le p_i \le n$)，表示初始奖励方案。

输入保证 $p_1, p_2, \dots, p_n$ 是一个长度为 $n$ 的排列，且 $\sum n \le 2 \times 10^5$。

输出格式

对于每个测试用例，输出一行，包含一个整数，即可能的奖励方案数量。答案可能非常大，你只需要输出答案对 $998244353$ 取模的结果。

样例

输入 1

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

输出 1

7

说明

为简单起见，我们使用 $[a_1, \dots, a_n]$ 来表示一个奖励方案，其中 $a_i$ 表示第 $i$ 位将军持有的城市。共有 $7$ 种可能的奖励方案：

• $[2, 1, 5, 4, 3]$，无需任何交换；
• $[1, 2, 5, 4, 3]$，通过将军 $(1, 2)$ 交换实现；
• $[2, 1, 5, 3, 4]$，通过将军 $(4, 5)$ 交换实现；
• $[1, 2, 5, 3, 4]$，按顺序通过将军 $(4, 5), (1, 2)$ 交换实现；
• $[2, 1, 3, 5, 4]$，按顺序通过将军 $(4, 5), (3, 4)$ 交换实现；
• $[1, 2, 3, 5, 4]$，按顺序通过将军 $(4, 5), (3, 4), (1, 2)$ 交换实现；
• $[2, 3, 1, 5, 4]$，按顺序通过将军 $(4, 5), (3, 4), (2, 3)$ 交换实现。