I - スコア 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 3 点

問題文

N 個の相異なる整数 A_1, A_2, \dots, A_N があります。
この中から K 個の整数を選びます。選び方の スコア を選んだ整数の総積として定義します。
K 個の整数を選ぶ方法は \binom{N}{K} 通りありますが、それらに対するスコアの総和を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^8
  • i \neq j ならば A_i \neq A_j
  • 入力される値は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3 2
2 3 5

出力例 1

31

K 個の整数を選ぶ方法およびそのスコアを列挙すると次のようになります。

  • A_1 = 2 と A_2 = 3 を選ぶ。スコアは 2 \times 3 = 6 となる。
  • A_1 = 2 と A_3 = 5 を選ぶ。スコアは 2 \times 5 = 10 となる。
  • A_2 = 3 と A_3 = 5 を選ぶ。スコアは 3 \times 5 = 15 となる。

入力例 2

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

出力例 2

902055

Score: 3 points

Problem Statement

You are given N distinct integers A_1, A_2, \dots, A_N.
You will choose K of them. The score of a choice is defined as the product of the chosen integers.
There are \binom{N}{K} possible ways to choose K integers.
Find the sum of their scores, and output the result modulo 998244353.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^8
  • If i \neq j, then A_i \neq A_j
  • All input values are integers

Input

The input is given from standard input in the following format:

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

3 2
2 3 5

Sample Output 1

31

The possible ways to choose K integers and their scores are:

  • Choose A_1 = 2 and A_2 = 3. The score is 2 \times 3 = 6.
  • Choose A_1 = 2 and A_3 = 5. The score is 2 \times 5 = 10.
  • Choose A_2 = 3 and A_3 = 5. The score is 3 \times 5 = 15.

Sample Input 2

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

Sample Output 2

902055