T200448 Call of The Void

[youtube官方动画](https://www.youtube.com/watch?v=bsCZJ893y2g) [TEAM_190搬运](https://www.bilibili.com/video/BV1Nh411r7dE) 又一次，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 $ 取模的结果即可。

**本题采用捆绑测试。** - 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（23pts）$ 1 \leq n \leq 1000 $。 - Subtask6（40pts）无特殊限制。 对于所有数据满足：$ 1 \leq n \leq 10^5 $，$ 1 \leq a_i \leq 10^6 $。