题目描述

李华有一副卡牌，每张卡牌有颜色、数字以及价值三个属性。每张卡牌的颜色可以用一个 $[1,n]$ 中的整数代表，同样的，每张卡牌上会写有一个 $[1,n]$ 之间的整数。根据数字和颜色的不同，这些卡牌被分为 $n^2$ 种。

为了方便表示，记一张颜色为 $x$，数字为 $y$ 的卡牌种类编号为 $(x-1)\times n+y$。在牌堆中，第 $i$ 种卡牌共有 $a_i$ 张，每张卡牌的价值为 $b_i$。

一开始，李华的手牌为空，初始积分为 $0$，李华会进行 $k$ 轮游戏。在每一轮的开始，李华会从牌堆里剩余的牌中随机取出一张牌，抽到每张牌的概率都是相等的。紧接着，如果手牌中含有与取出的牌数字或颜色相同的牌，那么李华会将所有的符合上述条件的牌加上原本取出的牌放回牌堆，反之则将抽出的牌置于手牌中。

每一轮结束后，李华的积分会加上其手牌中所有牌的价值，请帮李华求出 $k$ 轮后的期望总积分对 $998244353$ 取模后的值。

输入格式

第一行两个正整数 $n,k$ $(2\le n\le 4, 1\le k\le 10^9)$，代表颜色及数字的种类数和游戏轮数。

第二行为 $n^2$ 个整数 $a_i$ $(0\le a_i<998244353)$，代表牌堆里每种卡牌的数量。

第三行为 $n^2$ 个整数 $b_i$ $(0\le b_i<998244353)$，代表每种卡牌的积分。

数据保证不会出现所有卡牌可以同时置于手牌中的情况，且 $\sum a_i< 998244353$。

输出格式

输出一行一个整数，代表 $k$ 轮之后的总分期望值。

2 2
1 1 1 1
2 1 1 1

582309208

2 4
1 2 3 4
4 3 2 1

570601408

提示

对于第一个样例，最后得分与概率的对应如下：

期望得分为 $\frac{25}{12}$。

对于第二个样例，期望得分为 $\frac{5041}{810}$。