Hunting the Beast

Fix a starting set $S$ with $|S|=m$. All labels are symmetric, so after counting the number $F(n,m)$ of graphs where this fixed $S$ is successful, the final answer is

$$\binom{n}{m}F(n,m).$$

Call vertices in $S$ key vertices, and all other vertices non-key vertices.

Look at the SCC condensation DAG of the functional graph. A set of starts reaches every vertex iff every source SCC of this DAG contains a start. This is the standard DAG fact: every SCC is reachable from some source SCC, and no one can enter a source SCC from outside.

In a loopless functional graph, SCCs are directed cycles of length at least $2$, plus singleton vertices not on cycles. Therefore a bad source SCC is either:

• one non-key vertex with indegree $0$;
• a directed cycle made only of non-key vertices, with no incoming edge from outside the cycle.

So $S$ is successful iff there are no bad source SCCs.

Now use inclusion-exclusion over bad source SCCs. Suppose we choose a collection of bad source SCCs covering exactly $i$ non-key vertices. First choose those vertices in

$$\binom{n-m}{i}$$

ways.

For the chosen $i$ vertices, describe the chosen bad SCCs as a permutation:

• a fixed point means this vertex is an indegree-zero singleton source SCC;
• a cycle of length at least $2$ means those vertices form that directed cycle.

Each chosen SCC contributes a factor $-1$ from inclusion-exclusion.

Let a permutation $\pi$ on the $i$ chosen vertices have $c(\pi)$ cycles and $f(\pi)$ fixed points. The contribution of its internal structure is

$$(-1)^{c(\pi)}(n-i)^{f(\pi)}.$$

Why the $(n-i)^{f(\pi)}$? A fixed point is not a self-loop in the real graph. It represents an indegree-zero singleton, so its outgoing edge must go outside the chosen $i$ vertices, giving $n-i$ choices. Nontrivial cycle vertices have their outgoing edges fixed by the cycle.

Every vertex outside the chosen $i$ vertices must avoid pointing into them, otherwise the chosen SCC would not be a source. It also cannot point to itself. Thus each outside vertex has

$$n-i-1$$

choices, for a factor

$$(n-i-1)^{n-i}.$$

So we need the signed permutation sum

$$A_i=\sum_{\pi\in S_i}(-1)^{c(\pi)}(n-i)^{f(\pi)}.$$

Compute it by cycle generating functions. A fixed point has weight $-(n-i)x$, and every cycle of length $\ell\ge2$ has weight $-x^\ell/\ell$. Therefore

$$\sum_{i\ge0}\frac{A_i}{i!}x^i =\exp\left(-(n-i)x-\sum_{\ell\ge2}\frac{x^\ell}{\ell}\right).$$

For a fixed $i$, set $b=n-i-1$. Since

$$-\sum_{\ell\ge2}\frac{x^\ell}{\ell}=\log(1-x)+x,$$

we get

$$\sum_{i\ge0}\frac{A_i}{i!}x^i=(1-x)e^{-bx}.$$

Extracting the coefficient gives

$$A_i=(-1)^i(n-1)(n-i-1)^{i-1}$$

for $i\ge1$, and the same final product below also works for $i=0$. Therefore the contribution for this $i$ becomes

$$\binom{n-m}{i}(-1)^i(n-1)(n-i-1)^{n-1}.$$

Summing over all possible $i$:

$$F(n,m)=(n-1)\sum_{i=0}^{n-m}(-1)^i\binom{n-m}{i}(n-i-1)^{n-1}.$$

Finally,

$$\boxed{\text{ans}=\binom{n}{m}(n-1)\sum_{i=0}^{n-m}(-1)^i\binom{n-m}{i}(n-i-1)^{n-1}}$$

modulo $998244353$.

This also handles $m=n$: the sum has only $i=0$, so it becomes $(n-1)^n$, exactly the number of loopless functional graphs. For $n=1$, this is $0$, which is right because there is no valid outgoing edge. Tiny edge case, but it matters; off-by-one hell loves this stuff.

Precompute factorials and inverse factorials up to the maximum $n$. For each test case, evaluate the sum in $O(n-m)$ terms, using fast exponentiation for each power. Since the total $n$ over all tests is at most $10^6$, this is easily fine.

Complexity:

$$O(N+\sum (n-m)\log n)$$

with $O(N)$ memory, where $N$ is the maximum input $n$.