配点 : $800$ 点

問題文

$(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ に対して 次の問題を考え、その答えを $f(P)$ と書くことにします。

$(N+2)\times (N+2)$ のマス目があり、行には上から順に $0, 1, \ldots, N+1$ の番号が、列には左から順に $0, 1, \ldots, N+1$ の番号がつけられています。$i$ 行目・$j$ 列目のマスを $(i,j)$ と表します。

$(0,0)$ を出発して、右または下の隣り合うマスへの移動を繰り返すことで、$(N+1,N+1)$ まで移動する経路を考えます。ただし、$1\leq i\leq N$ に対してマス $(i, P_i)$ は通ってはいけません。このような経路は何通りあるでしょうか？

正の整数 $N$ および整数列 $A = (A_1, A_2, \ldots, A_N)$ が与えられます。各 $A_i$ は、$-1$ であるか、あるいは $1$ 以上 $N$ 以下の整数です。

$(1, 2, \ldots, N)$ の順列 $P = (P_1, P_2, \ldots, P_N)$ であって、$A_i\neq -1 \implies P_i = A_i$ を満たすものを考えます。そのようなすべての $P$ に対する $f(P)$ の総和を、$998244353$ で割った余りを求めてください。

制約

• $1\leq N\leq 200$
• $A_i = -1$ あるいは $1\leq A_i\leq N$
• $i\neq j$ に対し、$A_i\neq -1, A_j\neq -1$ ならば $A_i\neq A_j$

入力

入力は以下の形式で標準入力から与えられます。

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

出力

答えを出力してください。

4
1 -1 4 -1

41

$2$ つの順列 $P = (1,2,4,3)$ および $P = (1,3,4,2)$ に対する $f(P)$ の和が求めるものです。それぞれの $P$ の場合に、マス目において通れないマスを図示すると、次のようになります（通れるマス・通れないマスをそれぞれ . # で表しています）。

......         ......
  .#....         .#....
  ..#...         ...#..
  ....#.         ....#.
  ...#..         ..#...
  ......         ......
P=(1,2,4,3)    P=(1,3,4,2)

• 順列 $P = (1,2,4,3)$ の場合には $f(P) = 18$ です。
• 順列 $P = (1,3,4,2)$ の場合には $f(P) = 23$ です。

これらの和である $41$ が答えとなります。

4
4 3 2 1

2

この例では、計算対象となる順列 $P$ は $P = (4,3,2,1)$ のひとつです。

3
-1 -1 -1

48

• 順列 $P = (1,2,3)$ の場合には $f(P) = 10$ です。
• 順列 $P = (1,3,2)$ の場合には $f(P) = 6$ です。
• 順列 $P = (2,1,3)$ の場合には $f(P) = 6$ です。
• 順列 $P = (2,3,1)$ の場合には $f(P) = 12$ です。
• 順列 $P = (3,1,2)$ の場合には $f(P) = 12$ です。
• 順列 $P = (3,2,1)$ の場合には $f(P) = 2$ です。

これらの和である $48$ が答えとなります。