题目描述

有编号 $1$ 到 $N$ 的 $N$ 个球。球 $i$ 上写着一个整数 $A_i$。

对于一种从 $N$ 个球中选出若干个球的选法，定义该选法的得分为：所选球上写的数字之和的平方。

求从 $N$ 个球中选出 $K$ 个球的全部 $\binom{N}{K}$ 种选法的得分之和，对 $998244353$ 取模。

输入格式

输入以以下格式从标准输入给出：

• $N$ $K$
• $A_1$ $A_2$ $\dots$ $A_N$

输出格式

输出答案。

数据范围

• $1 \leq K \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• 输入中的所有值均为整数。

3 2
1 10 100

22422

从三个球中选出两个球有三种选法：选球 $1,2$ 的得分为 $(1+10)^2=121$，选球 $1,3$ 的得分为 $(1+100)^2=10201$，选球 $2,3$ 的得分为 $(10+100)^2=12100$。

答案是它们之和，$121+10201+12100=22422$。

5 2
10 10 20 20 20

10600

多个球上可能写着相同的数字。

2 1
998244353 998244353

0

求的是对 $998244353$ 取模后的和。

• 来源：AtCoder ABC 471 E

子任务设置

• 子任务 1（135 分）：$N \le 20$。
• 子任务 2（135 分）：$N \le 2000$。
• 子任务 3（180 分）：无特殊限制。