Below, we will use the following terms.

• For \(i\) where \(A_i\neq -1\), we call \((i, A_i)\) a forbidden square.
• We call a permutation satisfying \(P_i = A_i\) for each forbidden square \((i, A_i)\) simply a permutation.
• We call a path that does not visit forbidden squares simply a path.
• For a permutation \(P\), a path \(X\) and a square \((i, j)\), we say \(P\) and \(X\) collide at \((i, j)\) when \(P_i = j\) and \(X\) visits \((i,j)\).

Let \(K\) denotes the number of forbidden squares, and \(S\) denote the set of squares whose row ID and column ID are both between \(1\) and \(N\).

---

◆Applying the Inclusion-Exclusion Principle

What we want to find, \(\sum_P f(P)\), can be rephrased into the number of pairs \((P, X)\) of a permutation \(P\) and a path \(X\) that do not collide at any \((i,j)\in S\). Let us count it with the inclusion-exclusion principle.

For \(T\subset S\), a permutation \(P\) and a path \(X\), let us call the following condition the collision condition:

• if \((i,j)\in T\), \(P\) and \(X\) collide at \((i,j)\).

If \(g(T)\) is the number of tuples \((T, P, X)\) satisfying the collision condition for a fixed \(T\), the answer is \(\sum_T (-1)^{|T|} g(T)\) from the inclusion-exclusion principle.

Thus, we can compute the answer by counting tuples \((T, P, X)\) satisfying the collision condition for each \(|T|\).

---

◆Counting \(P\)

Let us count such tuples \((T, P, X)\). We say a pair \((T, X)\) of \(T\subset S\) and a path \(X\) is valid when the following conditions are satisfied:

• \(T\subset X\).
• \(T\) does not contain squares that share a row or a column with a forbidden square.
• \(T\) does not contain two squares that are in the same row or the same column.

For a \((T, X)\) that is not valid, no \((T, P, X)\) satisfies the collision condition. Thus, for \((T, X)\), we only need to consider valid ones.

When \((T, X)\) is valid, how many \((T, P, X)\) satisfies the collision condition? This is equal to the number of permutations under \(K + |T|\) conditions of the form \(P_i = j\) that are consistent with each other, so we can compute it as \((N - K - |T|)!\).

Particularly, the number of \(P\) only depends on \(|T|\). In the end, we have reduced the problem of counting \((T, P, X)\) satisfying the collision condition to a problem of counting valid \((T, X)\) for each \(|T|\).

---

◆Using DP

Let us count valid pairs \((T, X)\) for each \(|T|\), through the following DP:

• Consider the number of pairs \((T, X)\) of a path \(X\) to square \((i,j)\) and a set \(T\subset S\cap X\) that are valid and satisfy \(|T| = n\).
• Additionally, we have two boolean values \(\text{row}, \text{col}\in \{0,1\}\), according to whether we have chosen a element in \(T\) from the \(i\)-th row, and from the \(j\)-th row.
• Let \(\text{dp}[i, j, n, \text{row}, \text{col}]\) be the number of such pairs \((T, X)\), and sequentially compute them in some topological order on the squares \((i,j)\).

We can solve the problem in a total of \(O(N^3)\) time from all of the above.