AGC002F Leftmost Ball

题意：给你 种颜色的球，每个球有 个，把这 个球排成一排，把每一种颜色的最左边出现的球涂成白色(初始球不包含白色)，求有多少种不同的颜色序列。

答案对 取模。

，时限 。

---

考虑怎样的序列才可能是由上述规则生成的序列。

充要条件 ： 每个前缀的白球个数 其他颜色种类数

于是，在合法性问题上，我们只关心各个彩色球的第一次出现，以及白球。

考虑 ，向 个槽位中放球。

记 为放置了前 个白球，以及第一次出现最靠前的 种彩球，每种彩球放置 个的方案数。

显然，这里要求 。

考虑最靠前的第一个空位放置什么，转移如下：

• 放置一个白球

  一定合法。

• 放置一个彩球

  由 转移至 。

  个白球一定都在这个空位前面，所以当 则合法。

  选择一个未出现的颜色，方案数为 。

  在后面的空位中，选择 个用于放置其他的同色球，方案数为

复杂度 。注意需要特判 的情况。