1005. 今晚吃鸡扒

题目描述

农场主有 $n$ 个农场，编号为 $1\sim n$。

农场主一直苦于它的农场连通性不好，于是请你来重新设计农场之间的超空间通道。

你知道每一个农场都需要恰好向外连接 $3$ 个超空间通道才能保持农场的稳定，而两个农场之间最多只能有一条超空间通道，一条超空间通道必须连接两个不同的农场。

农场主想让你对于 $k=0\sim K$ 求出，有多少种不同的设计农场之间超空间通道的方案，使得恰有 $k$ 个无序三元组 $1\leq x<y<z\leq n$，满足编号为 $x,y,z$ 的农场之间两两存在一条超空间通道。由于数量可能很多，你需要将答案对 $\bmod$ 取模。

如果你能解决这个问题，农场主今晚会杀掉两只农场里的火鸡，请你吃它的拿手好菜：火鸡扒。

形式化地，对于 $k=0\sim K$，求满足以下条件的 $n$ 个点的有标号简单无向图数量，对 $\bmod$ 取模：

• 所有点的度数均为 $3$；
• 恰有 $k$ 个三元环。

输入格式

本题包含多组测试数据。

首先在第一行输入一个整数 $T$（$1\le T\le 30$）表示测试数据组数。

接下来对于每一组测试数据：

输入的唯一一行包含三个整数 $n,K,\bmod$（$1\leq n\leq10^3$，$0\leq K\leq\frac{n(n+1)}{2}$，$2\leq \bmod\leq10^9+7$）表示农场主的农场数量，$k$ 的上限与模数。

保证所有测试数据的 $n^2$ 之和不超过 $3\times10^6$。

输出格式

对于每一组测试数据，输出包含一行 $K+1$ 个非负整数表示 $k=0\sim K$ 时的答案。

样例输入

2
4 4 998244353
10 3 1964

样例输出

0 0 0 0 1
1036 1348 296 1684

来源：2026杭电多校-测试专用（南外） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1235&pid=1005