103584: [Atcoder]ABC358 E - Alphabet Tiles

Problem Statement

AtCoder Land sells tiles with English letters written on them. Takahashi is thinking of making a nameplate by arranging these tiles in a row.

Find the number, modulo $998244353$, of strings consisting of uppercase English letters with a length between $1$ and $K$, inclusive, that satisfy the following conditions:

• For every integer $i$ satisfying $1 \leq i \leq 26$, the following holds:
  • Let $a_i$ be the $i$-th uppercase English letter in lexicographical order. For example, $a_1 = $ A, $a_5 = $ E, $a_{26} = $ Z.
  • The number of occurrences of $a_i$ in the string is between $0$ and $C_i$, inclusive.

Constraints

• $1 \leq K \leq 1000$
• $0 \leq C_i \leq 1000$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$K$
$C_1$ $C_2$ $\ldots$ $C_{26}$

Output

Print the answer.

Sample Input 1

2
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 1

10

The $10$ strings that satisfy the conditions are A, B, C, AA, AB, AC, BA, BC, CA, CB.

Sample Input 2

358
1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Sample Output 2

64

Sample Input 3

1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

Sample Output 3

270274035

问题描述

AtCoder Land出售印有大写字母的瓷砖。Takahashi正考虑将这些瓷砖排成一行来制作一个名牌。

找出满足以下条件的、长度在$1$到$K$（含）之间的、由大写字母组成的字符串的数量，对$998244353$取模：

• 对于满足$1 \leq i \leq 26$的所有整数$i$，以下条件成立：
  • 令$a_i$为按字典序排序的第$i$个大写字母。例如，$a_1 = $ A，$a_5 = $ E，$a_{26} = $ Z。
  • 字符串中$a_i$出现的次数在$0$到$C_i$（含）之间。

约束

• $1 \leq K \leq 1000$
• $0 \leq C_i \leq 1000$
• 所有输入值都是整数。

输入

输入通过标准输入给出，格式如下：

$K$
$C_1$ $C_2$ $\ldots$ $C_{26}$

输出

打印答案。

样例输入1

2
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出1

10

满足条件的$10$个字符串是 A，B，C，AA，AB，AC，BA，BC，CA，CB。

样例输入2

358
1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

样例输出2

64

样例输入3

1000
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000

样例输出3

270274035