Background

Original problem link: https://oier.team/problems/X1E.

Problem Description

Xiao S has a tree with $n$ nodes. Each node has a light bulb.

Xiao S decides to perform $k$ flashing operations. When performing a flashing operation, he sends one flashing command to each light bulb using the computer host.

However, Xiao S's light bulbs are of poor quality, and only some of them can receive Xiao S's flashing command. Specifically, the light bulb on node $j$ has probability $p_{i,j}$ to receive Xiao S's $i$-th flashing operation.

Fortunately, Xiao S's different light bulbs can pass information to each other. Specifically, if a light bulb lies on the shortest path in the tree between two light bulbs that have received the information, then this light bulb can also perform the flashing operation (of course, the light bulbs that received the information will perform the flashing operation).

Define the beauty of light bulb $i$ as $a_{i,S}$, where $S$ is the set of operations that this light bulb performs.

Define the beauty of the whole tree as the product of the beauty of all light bulbs. Find the expected beauty of the whole tree, modulo $998244353$.

Input Format

The first line contains two positive integers $n,k$, representing the number of nodes of the tree and the number of operations.

The next $n-1$ lines each contain two positive integers $u,v$, representing an edge $(u,v)$ of the tree.

The next $k$ lines each contain $n$ non-negative integers. The $j$-th number in the $i$-th line represents $p_{i,j}$ modulo $998244353$.

The next $n$ lines each contain $2^k$ non-negative integers. The $(\sum_{i=1}^k2^{i-1}[i\in S])+1$-th number in the $i$-th line represents $a_{i,S}$. You can understand it as: in $a_{i,j}$, the $x$-th binary bit (from low to high) of $j-1$ indicates whether operation $x$ is included.

Output Format

One line with one non-negative integer, representing the expected beauty of the whole tree modulo $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

Hint

[Sample Explanation #1]

::cute-table

Therefore, the expected beauty is $\frac{1+2+3+4+6+24+12+24}{8}=\frac{19}{2}$, and modulo $998244353$ it equals $499122186$.

[Constraints]

This problem uses bundled testdata.

::cute-table{tuack}

For $100\%$ of the data: $1\leq n\leq100$, $1\leq k\leq8$, $1\leq u,v\leq n$. It is guaranteed that the given graph is a tree, and all other input values are integers in $[0,998244353)$.

Translated by ChatGPT 5