#P18605. Help Me to Get This Published

Help Me to Get This Published

Help Me to Get This Published

对一个n个顶点的完全图的每条边赋予一种颜色。如果不存在三条边颜色两两不同的三角形,就称它为Gallai着色。颜色的种类和名称没有预先限制。

顶点v的“颜色度”d(v),指与v相连的所有边一共使用了多少种不同颜色。整数序列(a1,...,an)被称为合法颜色度序列,当且仅当存在该完全图的一种Gallai着色,使每个带标号顶点i的颜色度恰为ai。

现在给出部分ai,其余位置用-1表示。请统计把这些-1替换为整数、最终得到合法颜色度序列的方法数,答案模998244353。

统计的是带标号的整数序列,不是着色方案。同一序列即使能被多种着色实现,也只计一次;未知位置填值不同就视为不同序列。

输入格式

第一行一个整数n,2<=n<=100。

第二行n个整数ai。每个ai为-1,或满足1<=ai<=n-1。-1表示该顶点颜色度未知。

输出格式

输出一个整数,表示合法填值方法数模998244353。

样例输入 1

2
1 -1

样例输出 1

1

样例输入 2

3
-1 -1 -1

样例输出 2

4

样例输入 3

6
5 -1 -1 -1 -1 -1

样例输出 3

120

样例说明

第一组只能填为(1,1)。第二组的四种合法序列是(1,1,1)、(1,2,2)、(2,1,2)、(2,2,1):第一种可用三条同色边,后三种可用两条同色边及一条其他颜色的边。