[ARC118E] Avoid Permutations

对于一个排列 $P$，定义 $F(P)$ 如下： 对于一个 $(N+2)\times (N+2)$ 的网格图，行列标号为 $0\sim N+1$，从 $(0,0)$ 走到 $(N+1,N+1)$ 在不经过 $(i,P_i)$ 情况下的方案数。 给定一个残缺的排列，对于其所有补全求函数之和。 translated by cszyf

[problemUrl]: https://atcoder.jp/contests/arc118/tasks/arc118_e $ (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 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

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

4
1 -1 4 -1

41

4
4 3 2 1

2

3
-1 -1 -1

48

### 制約 - $ 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 $ ### Sample Explanation 1 $ 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 $ が答えとなります。 ### Sample Explanation 2 この例では、計算対象となる順列 $ P $ は $ P\ =\ (4,3,2,1) $ のひとつです。 ### Sample Explanation 3 \- 順列 $ 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 $ が答えとなります。