/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
1 から N の番号がついた N 個のボールがあります。ボール i には整数 A_i が書かれています。
N 個のボールからいくつかのボールを選ぶ方法に対して、選んだボールに書かれた数の和の 2 乗をその選び方のスコアと定めます。
N 個のボールから K 個を選ぶ方法 \binom{N}{K} 通り全てのスコアの総和を 998244353 で割った余りを求めてください。
制約
- 1 \leq K \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 \dots A_N
出力
答えを出力せよ。
入力例 1
3 2 1 10 100
出力例 1
22422
3 個のボールから 2 個を選ぶ方法は 3 通りあり、ボール 1,2 を選んだときスコアは (1+10)^2=121、ボール 1,3 を選んだときのスコアは (1+100)^2=10201、ボール 2,3 を選んだときのスコアは (10+100)^2=12100 となります。
求める答えはこれらの和で 121+10201+12100=22422 となります。
入力例 2
5 2 10 10 20 20 20
出力例 2
10600
複数のボールに同じ数が書かれていることもあります。
入力例 3
2 1 998244353 998244353
出力例 3
0
998244353 で割った余りを求めてください。
Score : 450 points
Problem Statement
There are N balls numbered 1 to N. Ball i has an integer A_i written on it.
For a way of choosing some balls from the N balls, define the score of that choice as the square of the sum of the numbers written on the chosen balls.
Find the sum, modulo 998244353, of the scores of all \binom{N}{K} ways of choosing K balls from the N balls.
Constraints
- 1 \leq K \leq N \leq 2\times 10^5
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 \dots A_N
Output
Output the answer.
Sample Input 1
3 2 1 10 100
Sample Output 1
22422
There are three ways of choosing two balls from three balls: choosing balls 1,2 gives a score of (1+10)^2=121, choosing balls 1,3 gives a score of (1+100)^2=10201, and choosing balls 2,3 gives a score of (10+100)^2=12100.
The answer is the sum of these, 121+10201+12100=22422.
Sample Input 2
5 2 10 10 20 20 20
Sample Output 2
10600
Multiple balls may have the same number written on them.
Sample Input 3
2 1 998244353 998244353
Sample Output 3
0
Find the sum modulo 998244353.