H - Alphabet Tiles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

AtCoder Land では、アルファベットの書かれたタイルが販売されています。高橋君は、タイルを一列に並べてネームプレートを作ろうと考えました。

長さ 1 以上 K 以下の英大文字からなる文字列であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • 1 \leq i \leq 26 を満たす任意の整数 i について以下が成立する。
    • 辞書順で i 番目の英大文字を a_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

A, B, C, AA, AB, AC, BA, BC, CA, CB の 10 個の文字列が条件を満たします。

入力例 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

Score : 475 points

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