B. Card Game
time limit per test
10 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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 the range $$$[1,n]$$$, and similarly, each card will have an integer number in the range $$$[1,n]$$$ written on it. Based on the different numbers and colors, these cards are divided into $$$n^2$$$ types.

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

At the beginning, Li Hua's hand is empty, the initial score is $$$0$$$, and Li Hua will play $$$k$$$ rounds of the game. At the beginning of each round, Li Hua will randomly draw a card from the remaining cards in the deck, with an equal probability of drawing each card. Then, if the hand contains cards with the same number or color as the drawn card, Li Hua will return all cards that meet the above conditions along with the originally drawn card to the deck; otherwise, the drawn card will be put in the hand.

After each round, Li Hua's score will be increased by the value of all the cards in the hand. Please help Li Hua calculate the expected total score after $$$k$$$ rounds, taken modulo $$$998244353$$$.

Input

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 game rounds.

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

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

It is guaranteed that there will be no situation where all cards can be held in the hand at the same time, and $$$\sum a_i \lt 998244353$$$.

Output

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

Examples
Input
2 2
1 1 1 1
2 1 1 1
Output
582309208
Input
2 4
1 2 3 4
4 3 2 1
Output
570601408
Note

For the first example, the correspondence between the final score and the probability is as follows:

Score$$$1$$$$$$2$$$$$$3$$$$$$4$$$$$$5$$$
Probability$$$\frac 12$$$$$$\frac 16$$$$$$\frac 16$$$$$$\frac 1{12}$$$$$$\frac 1{12}$$$
The expected score is $$$\frac{25}{12}$$$.

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