#arc162e. [arc162_e]Strange Constraints

[arc162_e]Strange Constraints

题目描述

给定一个长度为 NN 的整数序列 A=(A1,A2,ldots,AN)A=(A_1,A_2,\\ldots,A_N),其中 AA 中的每个元素取值范围为 11NN

找出满足以下条件的长度为 NN 的整数序列 B=(B1,B2,ldots,BN)B=(B_1,B_2,\\ldots,B_N) 的数量,对 998244353998244353 取模:

  • 对于所有的 i=1,2,ldots,Ni=1,2,\\ldots,N,在序列 BB 中元素 ii 的出现次数不超过 AiA_i
  • 对于所有的 i=1,2,ldots,Ni=1,2,\\ldots,N,在序列 BB 中元素 BiB_i 的出现次数不超过 AiA_i

约束条件

  • 1leqNleq5001 \\leq N \\leq 500
  • 1leqAileqN1 \\leq A_i \\leq N
  • 所有输入值都是整数。

输入

从标准输入读取输入,其格式如下:

NN

A1A_1 A2A_2 ldots\\ldots ANA_N

输出

输出答案。


示例输入 1

3
1 2 3

示例输出 1

10

满足条件的序列有 1010 个:

  • (1,2,2)(1,2,2)
  • (1,2,3)(1,2,3)
  • (1,3,2)(1,3,2)
  • (1,3,3)(1,3,3)
  • (2,1,3)(2,1,3)
  • (2,3,1)(2,3,1)
  • (2,3,3)(2,3,3)
  • (3,1,2)(3,1,2)
  • (3,2,1)(3,2,1)
  • (3,2,2)(3,2,2)

示例输入 2

4
4 4 4 4

示例输出 2

256

满足条件的长度为 44 的整数序列共有 44=2564^4=256 种。


示例输入 3

5
1 1 1 1 1

示例输出 3

120

满足条件的序列包括 (1,2,3,4,5)(1,2,3,4,5) 的全排列,共有 5!=1205!=120 种。


示例输入 4

14
6 5 14 3 6 7 3 11 11 2 3 7 8 10

示例输出 4

628377683

请记得将答案对 998244353998244353 取模。