У вас есть \(c_1\) букв 'a', \(c_2\) букв 'b', ..., \(c_{26}\) букв 'z'. Вы хотите построить красивую строку длины \(n\) из них (очевидно, \(i\)-я буква может быть использована не более \(c_i\) раз). Каждое значение \(c_i\) больше \(\frac{n}{3}\).
Назовем строку красивой, если у нее нет ни одной палидромной непрерывной подстроки, длина которой нечетна и больше \(1\). Например, строка «abacaba» не является красивой, у нее есть несколько палиндромных подстрок, длина которых нечетна и больше \(1\) (одна из таких подстрок — «aca»). Другой пример: строка «abcaa» —- красивая.
Посчитайте количество различных строк, которые можно построить, и выведите его по модулю \(998244353\).
Выходные данные
Выведите одно целое число — количество различных строк, которые можно построить, взятое по модулю \(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
|
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
|
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
|
287489790
|