Illuminated Tree Beauty

You are given a tree with ( n ) nodes (numbered from (1) to (n)). Each node has a light bulb with an associated beauty factor ( c_i ). There will be ( k ) flash operations. In the ( i)-th operation, every node ( j ) independently receives a flash signal with probability ( p_{i,j} ) (given as an integer percentage, meaning the actual probability is ( p_{i,j}/100 )). However, the bulbs are low–quality: only some nodes receive the signal directly. Fortunately, the bulbs can communicate:

• Let ( R_i ) be the set of nodes that directly receive the flash signal in the ( i)-th operation. Each node in ( R_i ) will flash.
• Moreover, if ( R_i ) contains at least two nodes then any node that lies on the unique (tree) shortest path between any two nodes in ( R_i ) will also flash in that operation.
• If ( |R_i| \le 1 ) then only the nodes in ( R_i ) flash (if any).

When a node flashes in an operation, its beauty is multiplied by ( c_i ). Formally, if node ( i ) flashes in a set of operations ( S_i ), then its beauty becomes ( c_i^{|S_i|} ) (its initial beauty is (1)). The beauty of the entire tree is defined as the product of the beauty of every node.

Compute the expected beauty of the tree (over all random outcomes of the flash operations) modulo (998244353).

It is guaranteed that ( n ) and ( k ) are small (( n \le 15 ) and ( k \le 10 )).

Note: All probability calculations and the final answer should be done modulo (998244353). Remember that if an integer ( x ) appears in a fractional probability expression, it should be interpreted as ( x/100 ) modulo (998244353) (using the modular inverse of 100).

The key idea is to process each operation independently. For each operation, consider a random subset ( R ) (the nodes that directly receive the signal). Then, if ( |R| \ge 2 ) the actual set of nodes that flash is the union of all nodes on the shortest paths between every two nodes in ( R ); if ( |R| \le 1 ) the flashing set is exactly ( R ). For a given flashing set ( F ), its contribution is ( \prod_{i\in F} c_i ). The expected contribution for that operation is the sum over all subsets ( R \subseteq {1,2,\dots,n} ) of (\Big(\prod_{j\in R} p_j \cdot \prod_{j\notin R}(1-p_j)\Big) \times \Big(\prod_{i\in F} c_i\Big)). Since the operations are independent, the final answer is the product of the expectations for each operation modulo (998244353).

inputFormat

The input is given as follows:

Line 1: Two integers ( n ) and ( k )

Line 2: ( n ) integers ( c_1, c_2, \dots, c_n )

Next ( n-1 ) lines: Each line contains two integers ( u ) and ( v ) indicating an edge between nodes ( u ) and ( v ).

Then ( k ) lines follow. The ( i)-th of these lines contains ( n ) integers: ( p_{i,1}, p_{i,2}, \dots, p_{i,n} ), where each ( p_{i,j} ) is an integer between 0 and 100, representing the percentage probability (i.e. the actual probability is ( p_{i,j}/100 )) that node ( j ) receives the flash signal in operation ( i ).

outputFormat

Output a single integer: the expected beauty of the tree modulo (998244353).

sample

3 1
2 3 5
1 2
2 3
100 0 0

2