真让我给干出来了我去。已加入“超级无敌神仙炫酷无敌原神大王”豪华套餐。

首先考虑 $k=0$ 的情况，我们在置换环上考虑，每次操作为选择若干对不交点对，并让每对点交换出边，最终目标是全部为自环。

首先考虑计算 $f(A)$。

引理：对于一个 $n(n\ge 3)$ 元环，可以一次操作将其变为若干二元环和自环。

证明：不妨将 $n$ 元环按有向边方向编号 $1$ 到 $n$。那么构造方案 $(1,n),(2,n-1),...$ 即可（若 $n$ 为奇数会剩下一个点不操作），证毕。

而二元环可以一步变为两个自环，于是 $f(A)\le 2$。具体的，若原图只有自环，则 $f(A)=0$；若原图只有二元环，则 $f(A)=1$；否则，$f(A)=2$。

接下来考虑计算 $g(A)$。

对于 $f(A)\le 1$ 的情况显然 $g(A)=1$。下面只考虑 $f(A)=2$ 的情况。

通过大量手玩，我们可以发现多元环的变化流程都能被概括为：$n (n\ge 3)$ 元环 $\to$ 若干二元环 $\to$ 若干自环。

由于第二步的操作是固定的，我们注重考虑第一步的方案数。首先注意到在两个环长不同的环间操作一定不能全部拆解为二元环，那么我们只需考虑在同种环间的操作。

对于 $n(n\ge 3)$ 元环，“拆解”有两种形式：

1. 一个 $n$ 元环自主拆解，有 $n$ 种方案。对于 $n$ 为奇数，同引理的证明的构造方式，可任选不操作的点。对于 $n$ 为偶数，引理证明的构造有 $\frac{n}{2}$ 种方案，再加上 $(2,n),(3,n-1),...$ 这种构造（$1$ 和 $\frac{n}{2}+1$ 都不操作）也有 $\frac{n}{2}$ 种方案，故共有 $n$ 中方案。

2. 两个 $n$ 元环配对，有 $n$ 种方案。记两个环的编号分别为 $x_i,y_i$，那么构造操作 $(x_1,y_n),(x_2,y_{n-1}),...,(x_n,y_1)$ 即可，由于 $y$ 可以旋转 $n$ 次，故共有 $n$ 种方案。

那么如果我们有 $m$ 个 $n$ 元环，方案数记作 $f_{n,m}$。考虑最后一个环是否去配对，有递推：

$$f_{n,m}=n[f_{n,m-1}+(m-1)f_{n,m-2}]$$

对于二元环，由于它不需要专门去变为二元环，它的“拆解”有三种形式：

1. 第一步变为自环，第二步不操作。

2. 第一步不操作，第二步变为自环。

3. 第一步找另一个二元环配对，操作后仍为两个二元环，第二步变为自环。

通过计算发现，最终的式子与 $n\ge3$ 时的形式一样。

对于自环，与 $n\ge3$ 时的情况类似，最终的式子也一样，留做练习。

由于每种环长是独立的，对每种环长计算方案数并相乘即为答案。至此，我们得到了一个复杂度 $O(nk!)$ 的做法。

接下来的优化是相对容易的。

观察每个未知点所在的联通块，它一定是一条链，其中未知点为链尾，其他未知点只能连向链首。那么我们可以将它视作一个带点权的大点，这样就转化为了 $k$ 个大点之间相互的连边情况。

注意到我们只关心最终环的集合，而不关心其内部的连边方式，那么我们只需要枚举这 $k$ 个大点的划分即可，共有 $bell(k)\le 4213597$ 种，可以接受。

考虑一种划分 $P$，那么其对应排列的方案数为 $\prod_{x\in P}(x-1)!$，累加答案时作为附加系数即可。

对于这新形成的 $O(k)$ 的环，我们考虑直接去维护它们的加入。具体的，对于原图中完整的环，它们一定不包含未知点，所以是固定的，我们预处理它们的答案，以及每个环长的出现次数 $cnt_i$。当加入一个新环时，直接将答案乘上 $\frac{f_{i,cnt_i+1}}{f_{i,cnt_i}}$ 即可。由于我们不能迅速求一个 $f_{i,j}$，但注意到新的 $cnt_i' \le cnt_i+k$，那么我们只需要预处理出 $f_{i,cnt_i},...,f_{i,cnt_i+k}$ 即可，由于我们可以递推求 $f$，那么这是简单的。

至此，我们得到了复杂度 $O(bell(k)k+nk)$ 的做法。