「有标号二分图计数」

题意：若一张无向图可以被划分为两个点集 ，满足 内部无边，则称其为二分图。求 个点的有标号二分图数目。

答案对 取模，。

---

定义双色图：点染成黑白双色，且同色不连边的有标号图。显然，双色图是二分图。

记有标号二分图的组合类为 ，双色图的组合类是 。

注意到一个双色图黑白互换之后仍然是双色图，那么是否有 呢？

答案是否定的。考虑反映射，对于一个有标号二分图，若其分成多个连通分量，则每个连通分量都可以有各自的染色方案，并非只有 种对应的双色图。（对于一个二分图，若有 个连通分量，则将其黑白染色的方案数为 ）

记有标号联通二分图的组合类为 ，联通双色图的组合类是 。

此时就有 ，即 。

易得 。

则 。

综上 。

接下来的任务是求出 。

枚举有多少个点被染成黑色，易得 。

使用类似 Chirp Z-Transform 的方法可以卷积计算 ：