您希望构造一个由小写拉丁字母组成的字符串 s
，使得以下条件成立：对于 i和 j中的每一对索引 si=sj，这些索引的差值都是偶数，即 |i−j|mod2=0。构造任何字符串都非常简单，因此我们将得到一个由 26个数字组成的数组 c- 即字符串 s中每个字母出现的所需次数。因此，每 i∈[1,26]个拉丁字母中的 i个字母就应该出现 ci次。
你的任务是计算满足所有这些条件的不同字符串 s 的数量。由于答案可能非常庞大，所以请输出它的模数 998244353
要求索引的插值为偶数，相当于把字符的位置分成两类，奇数位置和偶数位置，一类字符串要么全部放在奇数
位置，要么全部放在偶数位置。我们先考虑选择哪些字母放直恰好能填满所有奇数位，这个可以用01背包求解，
自然地剩下的每一种字母一定能完整地放在偶数位置。
对于一种确定的情况，可以分别用全排列公式求助奇偶位的合法数目然后相乘即可
$$
\frac{odd!}{\prod_{i \in X} c_{i}!} \cdot \frac{even!}{\prod_{i \notin X} c_{i}!}
$$
整理得到，发现一但分组确定了，组合的数量是一样的
$$
\frac{odd! \cdot even!}{\prod_{i = 0}^{26} c_{i}!}
$$
最后乘上用背包求得的分组数量即可
$$
\frac{odd! \cdot even!}{\prod_{i = 0}^{26} c_{i}!} \cdot \text{dp}[odd]
$$
时间复杂度为 $O(S \cdot 26)$ .