У вас есть $$$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$$$.
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
422500
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
16900
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
287489790
Название |
---|