{"raw_statement":[{"iden":"problem statement","content":"You are given a sequence of positive integers $A = (A_1, A_2, \\dots, A_N)$ of length $N$, and a positive integer $T$.\nThere 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$.\nInitially, 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:\n\n*   Choose any location with a different color from your current one, and move there.\n\nCount the number of ways such that after all $T$ operations, you are back at the location you initially marked. Output the result modulo $998244353$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^5$\n*   $1 \\leq T \\leq 10^{18}$\n*   $1 \\leq A_i \\leq 10^9$\n*   All input values are integers"},{"iden":"partial score","content":"This problem has partial scoring:\n\n*   If you solve all datasets with $N \\leq 3 \\times 10^3$, you will earn $5$ points."},{"iden":"input","content":"The input is given from standard input in the following format:\n\n$N$ $T$\n$A_1$ $A_2$ $\\dots$ $A_N$"},{"iden":"sample input 1","content":"3 3\n2 1 2"},{"iden":"sample output 1","content":"4\n\nLet us label the locations as follows:\n\n*   The initially marked location: location $1$\n*   The other location painted with color $1$: location $2$\n*   The location painted with color $2$: location $3$\n*   The two locations painted with color $3$: locations $4$ and $5$\n\nThen, there are $4$ valid sequences of moves:\n\n*   $1 \\to 3 \\to 4 \\to 1$\n*   $1 \\to 3 \\to 5 \\to 1$\n*   $1 \\to 4 \\to 3 \\to 1$\n*   $1 \\to 5 \\to 3 \\to 1$"},{"iden":"sample input 2","content":"10 31415926535897932\n766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045"},{"iden":"sample output 2","content":"66487687"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}