#P6940. 分身

    ID: 6771 传统题 1500ms 512MiB 尝试: 2 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-组合数学Lindström–Gessel–Viennot 引理线性代数与代数行列式函数基底变换多项式与生成函数卷积转化NTT数论模逆元快速幂CF2600

分身

分身(path)

时间限制:2秒;空间限制:512 MiB。

题目描述

你有 nn 个分身和 nn 个目的地。街区构成网格图,用 (i,j)(i,j) 表示一个街区。第 ii 个分身从 (0,ai)(0,a_i) 出发,前往第 ii 个目的地 (i,0)(i,0)。

每一步只能从 (i,j)(i,j) 走到 (i+1,j)(i+1,j) 或 (i,j−1)(i,j-1)。任意两个分身的路径不能经过同一个街区,起点和终点也包括在内。

求所有分身到达各自目的地且路径两两不相交的方案数。两种方案不同,当且仅当至少一个分身的路径不同。答案对 998244353998244353 取模。

输入格式

从标准输入读入。第一行一个整数 nn;第二行 nn 个整数 aia_i。

输出格式

向标准输出写出一行,一个整数,表示答案。

样例输入

2
1 2

样例输出

3

数据范围

所有数据满足 ai≤ai+1a_i\le a_{i+1},n≤5×105n\le5\times10^5,0≤ai<1060\le a_i<10^6。