Card Matching Game Expected Score

Li Hua has a deck of cards. Each card has three attributes: color, number, and value. The color and number are both integers in the range \( [1,n] \). Thus, there are \( n^2 \) types of cards. For convenience, we number a card of color \( x \) and number \( y \) as \( (x-1)\times n+y \). For the \( i\)-th type (\( 1\le i\le n^2 \)), there are \( a_i \) cards in the deck, and each card has a value of \( b_i \).

Initially, Li Hua’s hand is empty and his score is 0. He will perform \( k \) rounds. In each round, he randomly draws one card from the remaining deck (each card is equally likely). Immediately after drawing, if his hand already contains any card whose color or number matches that of the drawn card, then he returns the drawn card together with all cards in his hand that share the same color or number back into the deck. Otherwise, he adds the drawn card to his hand.

At the end of each round, Li Hua’s score increases by the sum of the values of all cards in his hand. Compute the expected total score after \( k \) rounds modulo \( 998244353 \).

inputFormat

The first line contains two integers \( n \) and \( k \).

The second line contains \( n^2 \) integers \( a_1, a_2, \ldots, a_{n^2} \) where \( a_i \) is the count of the \( i\)-th type of card.

The third line contains \( n^2 \) integers \( b_1, b_2, \ldots, b_{n^2} \) where \( b_i \) is the value of each card of type \( i \).

outputFormat

Output a single integer: the expected total score after \( k \) rounds modulo \( 998244353 \).

sample

2 1
1 1 1 1
1 2 3 4

expected_output_1