First, the \(2^{(\text{number of cycles})}\) in the original problem is cumbersome, so we consider an appropriate reformulation. One possible reformulation is as follows:

For a functional graph \(G\) and a vertex set \(S \subseteq \{1,2,\dots,N\}\) (possibly empty), define \(f(G, S)\) as follows.

• If at least one of the following conditions holds, then \(f(G, S) = 0\):
  • There exists some \(i\) \((2 \leq i \leq N)\) such that \(G\) contains the edge \(i \to p_i\).
  • \(G\) contains an edge \(u \to v\) such that \(u \in S\) and \(v \notin S\).
  • A vertex \(u \in S\) doesn’t lie on a cycle in \(G\)
• Otherwise, the subgraph of \(G\) induced by \(S\) consists solely of several vertex-disjoint cycles. Let \(x\) be the number of even-length cycles in this induced subgraph, and let \(f(G, S) = (-1)^x\).

Compute the sum, modulo \(998244353\), of \(f(G, S)\) over all pairs \((G, S)\).

In this reformulation, one can check that the sum of \(f(G, S)\) is \(2^{(\text{number of cycles in } G)}\) for a good graph \(G\), and the sum is \(0\) for a graph \(G\) that is not good. Thus, this reformulation is valid.

Let us consider the sum of \(f(G, S)\) when the vertex set \(S\) is fixed. It reduces to the answer to the following subproblem multiplied by a constant factor:

Consider a permutation graph \(G'\) with \(m\) vertices. Define \(f(G') = (-1)^{(\text{number of even-length cycles in } G')}\).
However, some edges are banned: if \(G'\) contains any banned edge, then \(f(G') = 0\). The collection of banned edges forms a DAG in which every vertex has outdegree at most \(1\).
What is the sum of \(f(G')\) over all possible permutation graphs \(G'\)?

Let us solve this subproblem. First, consider the case with no banned edges. One can show (for instance using generating-function arguments or even/odd-permutation arguments) that the answer is \(1\) if \(m \leq 1\), and \(0\) otherwise.

When there are banned edges, we apply the principle of inclusion-exclusion over the set of banned edges. We observe:

• If the banned-edge set forms a path of length \(m-1\), the answer is \(1\).
• Otherwise, it is \(0\).

Thus, the subproblem is solved.

Applying this partial result, it follows that the sum of \(f(G, S)\) for a fixed \(S\) is \(0\) in most cases. The cases where it is nonzero are when \(S\) is empty or the subgraph of the rooted tree \(T\) induced by \(S\) forms a path-graph in the form \(i - p_i - p_{p_i} - \dots\). There are at most \(\mathrm{O}(N^2)\) such cases. Moreover, we can compute the sum of all \(f(G, S)\) in \(\mathrm{O}(N)\) time by using prefix sums.

Implementation of the above solves the problem in \(\mathrm{O}(N)\) time, which is sufficiently fast.