AT_fps_24_t カラフル

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 $ .

The input is given from standard input in the following format: > $ N $ $ T $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

Print the answer.

### Partial Score This problem has partial scoring: - If you solve all datasets with $ N \leq 3 \times 10^3 $ , you will earn $ 5 $ points. ### Sample Explanation 1 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 $ ### 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