题目背景

youtube官方动画 TEAM_190搬运

又一次，sans 倒在了那把红刀之下。

*真的就没有办法阻止这场屠杀吗？

玩家再次重启了世界，没有人记得自己曾经被杀死过，没有人记得自己在钟声敲响时干了什么。

sans 再次在雪镇游走，等待着玩家的再次到来。不过，他在等待的时候，遇到了一扇以前从来没有见过的门。

他很好奇门里有什么，推开了门，看见里面有一个身影。那个身影用手说道：

*【链接已屏蔽】

sans 想了想，接受了那个身影的邀请。

那个身影站了起来，带着 sans 走到了一个阴暗而又潮湿的地方。

sans 想了起来，这个阴暗而潮湿的地方，是 Alphys 的实验室！

那么这个身影，就是。。。

那个身影走到了控制台前，需要输入密码。不过那个身影表示他记不起密码了。

sans 走了过来，利用时间线轻松地解决了控制台的密码。

此时，sans 看见前方的门打开了。走进去后看见了一台巨大的机器。那个身影告诉了 sans 他的计划。

于是，他们在实验室等待着玩家的到来。不过，这次 sans 将会充满决心。

......

战胜了玩家后，sans 利用决心的力量和 Asgore 的七个灵魂回到了地表。它们很高兴能够再次看见天空中正在下落的太阳。

当 sans 再次回想起那次的遭遇时，很想知道，他利用时间线轻松破解的密码，原本应该如何破解。

题目描述

控制台会给你一颗节点数量为 $n$ 的树，第 $i$ 个点的点权为 $a_i$。

定义 $dis(u,v)$ 为 $u$ 到 $v$ 的路径上所有点的点权之积。

再定义函数 $g$ 满足：

$$g(n)=(\sum_{d^2|n}\mu(\frac n {d^2})) \times \varphi(n) $$

控制台的密码为 $\prod_{i=1}^n\prod_{j=i+1}^ng(dis(i,j))$。

输入格式

第一行一个数 $n$。

接下来 $n-1$ 行，每行两个数 $u,v$，代表 $u$ 和 $v$ 之间有一条边连接。

再接下来一行一共 $n$ 数，第 $i$ 个数即为 $a_i$。

输出格式

一行，控制台的密码。由于结果可能太大，你只需要输出其对 $998244353$ 取模的结果即可。

4
1 2
1 3
2 4
8 6 10 5

511705067

提示说明

本题采用捆绑测试。

• Subtask1（3pts）$ 1 \leq n \leq 10,1 \leq \prod_{i=1}^n a_i \leq 10^{18} $。
• Subtask2（7pts）存在一个 $p$，使得对于每一个 $i$ 存在一个 $k_i$ 满足 $a_i=p^{k_i}$。
• Subtask3（13pts）给出的数为一条链。
• Subtask4（14pts）存在一个度数为 $n-1$ 的节点。
• Subtask5（15pts）$1 \leq n \leq 100$。
• Subtask6（18pts）$1 \leq n \leq 1000$。
• Subtask7（40pts）无特殊限制。

对于所有数据满足：$1 \leq n \leq 10^5,1 \leq a_i \leq 10^6$。