Problem Description

Li Hua has a deck of cards. Each card has three attributes: color, number, and value. The color of each card can be represented by an integer in $[1,n]$, and similarly, each card also has a number that is an integer in $[1,n]$. Based on different numbers and colors, these cards are divided into $n^2$ types.

For convenience, define that the type ID of a card with color $x$ and number $y$ is $(x-1)\times n+y$. In the deck, there are $a_i$ cards of type $i$, and the value of each card of type $i$ is $b_i$.

At the beginning, Li Hua has an empty hand and an initial score of $0$. Li Hua will play for $k$ rounds. At the start of each round, Li Hua randomly draws one card from the remaining cards in the deck, and each remaining card has an equal probability of being drawn. Next, if the hand contains any card whose number or color is the same as the drawn card, then Li Hua returns all cards in the hand that satisfy the above condition, together with the drawn card, back into the deck. Otherwise, the drawn card is placed into the hand.

After each round ends, Li Hua's score increases by the sum of the values of all cards currently in the hand. Please compute the expected total score after $k$ rounds, and output it modulo $998244353$.

Input Format

The first line contains two positive integers $n,k$ $(2\le n\le 4, 1\le k\le 10^9)$, representing the number of colors and numbers, and the number of rounds.

The second line contains $n^2$ integers $a_i$ $(0\le a_i<998244353)$, representing the number of cards of each type in the deck.

The third line contains $n^2$ integers $b_i$ $(0\le b_i<998244353)$, representing the score value of each type of card.

The testdata guarantees that the situation where all cards can be placed into the hand at the same time will not occur, and $\sum a_i< 998244353$.

Output Format

Output one integer on one line, representing the expected total score after $k$ rounds.

2 2
1 1 1 1
2 1 1 1

582309208

2 4
1 2 3 4
4 3 2 1

570601408

Hint

For the first sample, the correspondence between the final score and its probability is as follows.

The expected score is $\frac{25}{12}$.

For the second sample, the expected score is $\frac{5041}{810}$.

Translated by ChatGPT 5