← 返回题目列表

Codeforces · 1487/G

G. 字符串计数

中文机器翻译题面 查看原题

您有 $$$c_1$$$ 字母“a”、$$$c_2$$$ 字母“b”、...、$$$c_{26}$$$ 字母“z”。您想从它们构建一个长度为 $$$n$$$ 的漂亮字符串(显然,您不能使用第 $$$i$$$ 个字母超过 $$$c_i$$$ 次)。每个 $$$c_i$$$ 都大于 $$$\frac{n}{3}$$$。

如果一个字符串中不存在奇数长度大于 $$$1$$$ 的回文连续子串,则该字符串被称为漂亮字符串。例如,字符串“abacaba”并不美观,它有几个奇数长度大于$$$1$$$的回文子串(例如“aca”)。另一个例子:字符串“abcaa”很漂亮。

计算您可以构建的不同字符串的数量,并打印对 $$$998244353$$$ 取模的答案。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 400$$$)。

第二行包含 $$$26$$$ 整数 $$$c_1$$$, $$$c_2$$$, ..., $$$c_{26}$$$ ($$$\frac{n}{3} < c_i \le n$$$)。

输出

打印一个整数 — 您可以构建的字符串数量,以 $$$998244353$$$ 为模。

示例

输入 #1

4
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

输出 #1

422500

输入 #2

3
2 2 2 2 2 2 3 3 3 2 2 2 2 2 2 3 3 3 2 2 3 2 2 3 2 2

输出 #2

16900

输入 #3

400
348 322 247 158 209 134 151 267 268 176 214 379 372 291 388 135 147 304 169 149 193 351 380 368 181 340

输出 #3

287489790