ARC102C Stop. Otherwise...

题意：有 个骰子，每个骰子有 个面，上面有 。

现在对于 中的每一个数 ，求出任意投这个 个骰子使得不存在任意两个骰子的点数和为 的方案数。

骰子之间本质相同（无标号）。

答案对 取模，，时限 。

---

只考虑 时的情况，另一侧的方案数是对称的。

对于一个给定的 ，将数 两两配对，两者中只能出现一个。

特殊地， 至多只能出现一次。

其余没有配对的数则无限制。

对子的个数是 ，而没配对的数的个数是 。

无标号计数，使用 OGF。

对于至多出现一次的数：

对于一个对子：

对于一个没有配对的数：

将所有生成函数乘起来，答案为 ：

考虑如何求

分子分母的展开式都是容易表示的，暴力计算卷积即可。

复杂度 。