String Counting

10000ms

1048576K

Description:

You have $$$c_1$$$ letters 'a', $$$c_2$$$ letters 'b', ..., $$$c_{26}$$$ letters 'z'. You want to build a beautiful string of length $$$n$$$ from them (obviously, you cannot use the $$$i$$$-th letter more than $$$c_i$$$ times). Each $$$c_i$$$ is greater than $$$\frac{n}{3}$$$.

A string is called beautiful if there are no palindromic contiguous substrings of odd length greater than $$$1$$$ in it. For example, the string "abacaba" is not beautiful, it has several palindromic substrings of odd length greater than $$$1$$$ (for example, "aca"). Another example: the string "abcaa" is beautiful.

Calculate the number of different strings you can build, and print the answer modulo $$$998244353$$$.

Input:

The first line contains one integer $$$n$$$ ($$$3 \le n \le 400$$$).

The second line contains $$$26$$$ integers $$$c_1$$$, $$$c_2$$$, ..., $$$c_{26}$$$ ($$$\frac{n}{3} < c_i \le n$$$).

Output:

Print one integer — the number of strings you can build, taken modulo $$$998244353$$$.

Sample Input:

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

Sample Output:

Sample Input:

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

Sample Output:

Sample Input:

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

Sample Output:

287489790

Informação

Provedor Codeforces

Código CF1487G