题目描述

六面骰子专门店“Saikoroya”出售$N$个骰子。第$i$个骰子（复数为骰子）的每一面都写着$A_{i,1},A_{i,2},\\ldots,A_{i,6}$，并且价格为$C_i$。

Takahashi打算选择恰好$K$个并购买它们。

目前，“Saikoroya”正在进行促销活动：Takahashi可以将购买的每个骰子都投掷一次，并要求金额等于骰子所显示数字之和的平方。在这里，每个骰子均以相同的概率和独立地显示六个数字中的一个。

通过正确选择要购买的$K$个骰子，使得（他要支付的金额）-（他购买的$K$个骰子的金额之和）的期望值最大化。将最大化的期望值按模$998244353$输出。

求模$998244353$的期望值定义

我们可以证明所求的期望值始终是一个有理数。此外，在这个问题的约束条件下，可以用不可约分数$\\frac{y}{x}$表示所求的期望值，其中$x$不能被$998244353$整除。

在这种情况下，我们可以唯一确定一个介于$0$和$998244352$（包括这两个数）之间的整数$z$，使得$xz \\equiv y \\pmod{998244353}$。输出该$z$。

约束条件

• $1 \\leq N \\leq 1000$
• $1 \\leq K \\leq N$
• $1 \\leq C_i \\leq 10^5$
• $1 \\leq A_{i,j} \\leq 10^5$
• 输入中的所有值都是整数。

输入

从标准输入读入输入数据，输入格式如下：

$N$ $K$ $C_1$ $C_2$ $\\ldots$ $C_N$ $A_{1,1}$ $A_{1,2}$ $\\ldots$ $A_{1,6}$ $\\vdots$ $A_{N,1}$ $A_{N,2}$ $\\ldots$ $A_{N,6}$

输出

打印答案。

示例输入1

3 2
1 2 3
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3

示例输出1

20

如果他购买第$2$和第$3$个骰子，则（他要支付的金额）-（他购买的$K$个骰子的金额之和）的期望值等于$(2 + 3)^2 - (2 + 3) = 20$，这是最大的期望值。

示例输入2

10 5
2 5 6 5 2 1 7 9 7 2
5 5 2 4 7 6
2 2 8 7 7 9
8 1 9 6 10 8
8 6 10 3 3 9
1 10 5 8 1 10
7 8 4 8 6 5
1 10 2 5 1 7
7 4 1 4 5 4
5 10 1 5 1 2
5 1 2 3 6 2

示例输出2

1014