Problem Description

Li Hua has a deck of cards, each with three attributes: color, number, and value. Each card's color and number can be represented by an integer in the range $[1, n]$. These cards are categorized into $n^2$ types based on their color and number.

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

Initially, Li Hua's hand is empty, and his score is zero. He will play the game for $k$ rounds. At the start of each round, Li Hua randomly draws one card from the remaining deck, with each card having an equal probability of being drawn. If there are cards in his hand that match the drawn card's color or number, he will return all such matching cards along with the drawn card to the deck. Otherwise, he will add the drawn card to his hand.

After each round, Li Hua's score increases by the total value of all cards in his hand. Help Li Hua calculate the expected total score after $k$ rounds, 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 color and number types, and the number of rounds, respectively.

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 value of each type of card.

The data guarantees that it is impossible for all cards to be in Li Hua's hand at the same time, and $\sum a_i < 998244353$.

Output Format

Output a single integer, representing the expected total score after $k$ rounds, modulo $998244353$.

Sample Input and Output

Sample Input #1

2 2
1 1 1 1
2 1 1 1

Sample Output #1

582309208

Sample Input #2

2 4
1 2 3 4
4 3 2 1

Sample Output #2

570601408

Notes

For the first sample, the final scores and their probabilities are as follows:

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

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

见题面 Input 部分

见题面 Output 部分