题目描述

小 S 有一棵 $n$ 个点的树。每个点上有一个灯泡。

小 S 决定进行 $k$ 次闪灯操作。执行闪灯操作时，他会用电脑主机给每个灯泡发送一次闪灯操作。

然而，小 S 的灯泡是劣质品，只有一部分的灯泡可以收到小 S 的闪灯操作。具体地，第 $j$ 个点上的灯泡有 $p_{i,j}$ 的概率收到小 S 的第 $i$ 次闪灯操作。

好在，小 S 的不同灯泡之间有信息传递功能。具体地，如果一个灯泡在两个收到信息的灯泡的树上最短路径上，这个灯泡也能执行闪灯操作（当然，收到信息的灯泡会执行闪灯操作）。

定义一个灯泡 $i$ 的美丽度为 $a_{i,S}$，其中 $S$ 为这个灯泡执行闪灯操作的操作集合。

定义整棵树的美丽度为每个灯泡美丽度的乘积。求整棵树美丽度的期望，对 $998244353$ 取模。

输入格式

第一行两个正整数 $n,k$，表示树的点数与操作次数。

接下来 $n-1$ 行每行两个正整数 $u,v$，表示树上的一条边 $(u,v)$。

接下来 $k$ 行每行 $n$ 个非负整数，第 $i$ 行第 $j$ 个表示 $p_{i,j}$ 对 $998244353$ 取模后的值。

接下来 $n$ 行每行 $2^k$ 个非负整数，第 $i$ 行第 $(\sum_{i=1}^k2^{i-1}[i\in S])+1$ 个表示 $a_{i,S}$。可以理解为 $a_{i,j}$ 中 $j-1$ 的从低到高第 $x$ 个二进制位代表是否有 $x$ 操作。

输出格式

一行，一个非负整数，表示整棵树的美丽度的期望，对 $998244353$ 取模。

3 1
1 2
2 3
499122177 499122177 499122177
1 2
1 3
1 4

499122186

10 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
1 1 4 5
1 4 1 9
1 9 8 1
0 1 1 4
5 1 4 1
9 1 9 8
1 0 9 9
8 2 4 4
3 5 3 1
2 3 4 5

497209006

提示

【样例解释 #1】

故美丽度的期望是 $\frac{1+2+3+4+6+24+12+24}{8}=\frac{19}{2}$，对 $998244353$ 取模后为 $499122186$。

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据：$1\leq n\leq100$，$1\leq k\leq8$，$1\leq u,v\leq n$，保证给出数据为一棵树，保证其他输入数据均为 $[0,998244353)$ 中的整数。