T - カラフル 解説 /

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

配点 : 7 点

問題文

長さ N の正整数列 A = (A_1, A_2, \dots, A_N) および正整数 T が与えられます。
\sum_{i=1}^N A_i か所の地点があります。異なる地点は互いに区別できます。各地点には整数で表される色で塗られていて、色 i で塗られた地点は A_i か所あります。
はじめ、あなたは色 1 で塗られた地点を 1 か所選び、その地点に移動して印をつけます。その後、あなたは次の操作をちょうど T 回繰り返します。

  • 自分が今いる地点とは異なる色の地点を自由に選び、その地点に移動する。

T 回全ての操作が終了した時点ではじめに印をつけた地点にいるような移動の方法の個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq T \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • 入力される値は全て整数

部分点

この問題には部分点が設定されている。

  • N \leq 3 \times 10^3 を満たすデータセットに正解した場合、5 点が与えられる。

入力

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

N T
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

3 3
2 1 2

出力例 1

4
  • はじめに移動して印をつけた地点を地点 1、
  • 地点 1 でない色 1 で塗られた地点を地点 2、
  • 色 2 で塗られた地点を地点 3、
  • 色 3 で塗られた 2 か所の地点をそれぞれ地点 4 と地点 5

と呼ぶことにします。この時、条件を満たす移動は次の 4 通りです。

  • 地点 1 \to 地点 3 \to 地点 4 \to 地点 1
  • 地点 1 \to 地点 3 \to 地点 5 \to 地点 1
  • 地点 1 \to 地点 4 \to 地点 3 \to 地点 1
  • 地点 1 \to 地点 5 \to 地点 3 \to 地点 1

入力例 2

10 31415926535897932
766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045

出力例 2

66487687

Score: 7 points

Problem Statement

You are given a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N, and a positive integer T.

There are \sum_{i=1}^N A_i distinct locations. Each location is painted with a color represented by an integer, and there are exactly A_i locations painted with color i.

Initially, you choose one of the locations painted with color 1, move to that location, and mark it. Then, you repeat the following operation exactly T times:

  • Choose any location with a different color from your current one, and move there.

Count the number of ways such that after all T operations, you are back at the location you initially marked. Output the result modulo 998244353.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq T \leq 10^{18}
  • 1 \leq A_i \leq 10^9
  • All input values are integers

Partial Score

This problem has partial scoring:

  • If you solve all datasets with N \leq 3 \times 10^3, you will earn 5 points.

Input

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

N T
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

3 3
2 1 2

Sample Output 1

4

Let us label the locations as follows:

  • The initially marked location: location 1
  • The other location painted with color 1: location 2
  • The location painted with color 2: location 3
  • The two locations painted with color 3: locations 4 and 5

Then, there are 4 valid sequences of moves:

  • 1 \to 3 \to 4 \to 1
  • 1 \to 3 \to 5 \to 1
  • 1 \to 4 \to 3 \to 1
  • 1 \to 5 \to 3 \to 1

Sample Input 2

10 31415926535897932
766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045

Sample Output 2

66487687