给定一个长度为 $N$ 的正整数序列 $A = (A_1, A_2, \dots, A_N)$，以及一个正整数 $T$。

共有 $\sum_{i=1}^N A_i$ 个互不相同的位置。每个位置被涂上了一种颜色，颜色用整数表示，恰好有 $A_i$ 个位置被涂成颜色 $i$。

最开始，你可以任选一个被涂成颜色 $1$ 的位置，移动到该位置，并将其做上标记。之后，你要恰好执行 $T$ 次如下操作：

• 从当前位置出发，任选一个颜色与当前不同的位置并移动过去。

请计算，总共有多少种方案使得在完成这 $T$ 次操作后，你又回到了最初标记的位置。请将结果对 $998244353$ 取模后输出。

输入从标准输入读入，格式如下：

$N$ $T$ $A_1$ $A_2$ $\dots$ $A_N$

请输出答案。

部分分数

本题包含部分分数：

• 如果能解决 $N \leq 3 \times 10^3$ 的全部数据集，将获得 $5$ 分。

样例说明 1

我们给位置编号如下：

• 初始打标记的位置：位置 $1$
• 颜色 $1$ 的另一个位置：位置 $2$
• 颜色 $2$ 的位置：位置 $3$
• 颜色 $3$ 的两个位置：位置 $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$

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq T \leq 10^{18}$
• $1 \leq A_i \leq 10^9$
• 所有输入均为整数。

由 ChatGPT 5 翻译