题目背景

大陆上的 $n$ 座驿站由 $n-1$ 条道路连成一棵树，道路有各自的通行时间。三位信使从各自的城市出发，约定在某座驿站会合。

题目描述

设树 $T = (V, E)$，其中 $|V| = n$，每条边 $e$ 有正整数边权 $w_e$（即通行时间）。

信使甲、乙、丙分别有候选出发集合 $A, B, C \subseteq V$，三个集合均非空。三人在各自候选集合中等概率、独立随机地选择一个驿站作为出发点（同一驿站可被多人同时选中；一个驿站也可以同时属于多个集合）。

设三人选择的出发点为 $a \in A$、$b \in B$、$c \in C$。会合代价定义为三人各自路程之和的最小可能值，即连接 $a, b, c$ 三点的最小连通子图的边权总和，记为 $\operatorname{cost}(a, b, c)$。

请求出会合代价的期望值：

$$\mathbb{E}[\operatorname{cost}(a, b, c)] = \frac{1}{|A|\,|B|\,|C|} \sum_{a \in A} \sum_{b \in B} \sum_{c \in C} \operatorname{cost}(a, b, c)$$

设该期望值可写成最简分数 $\dfrac{p}{q}$（$p$ 为整数，$q > 0$）。可以证明 $q$ 不被 $998244353$ 整除，请输出 $p \cdot q^{-1} \bmod 998244353$，结果落在 $[0, 998244353)$ 内。

输入格式

第一行一个整数 $n$。

接下来 $n-1$ 行，每行三个整数 $u, v, w$，表示一条连接驿站 $u, v$、通行时间为 $w$ 的边。

接下来三行，每行一个长度为 $n$ 的 $0/1$ 字符串，依次表示集合 $A, B, C$：第 $i$ 个字符为 $1$ 表示驿站 $i$ 属于该集合。保证三个集合均非空。

输出格式

一行一个整数，表示答案对 $998244353$ 取模的结果。

样例

样例 1 输入

3
1 2 2
2 3 3
100
010
001

样例 1 输出

5

样例说明：三人出发点确定为 $(1, 2, 3)$，最小连通子树为整棵树，代价为 $2 + 3 = 5$。

样例 2 输入

3
1 2 2
2 3 3
110
110
001

样例 2 输出

499122181

样例说明：期望为 $\dfrac{9}{2}$，而 $9 \times 2^{-1} \equiv 499122181 \pmod{998244353}$。

数据范围与提示

对于全部数据：$2 \le n \le 2 \times 10^5$，$1 \le w \le 10^9$。

时间限制：2 秒；内存限制：1024 MB。