不希望有质量的问题沉没，故此特捞。

---

如果在本人发第一个帖子之前没有相似的题目，则该题是本人原创，本人保留有版权。

第一个帖子以及第二个帖子

---

附简单题面：

题目描述

给定一个含 $n$ 个数字的一个排列，其中数字可能有重复，求有多少种排列方案（包括原排列）使得该排列方案中恰有 $k$ 个 位置 与原来给定的排列方案不同。答案对大质数取模。

输入输出

输入格式:第一行一个正整数 $n$ 表示给定排列元素个数。第二行 $n$ 个整数表示给定排列。

输出格式：输出一行 $n+1$ 个数，第 $i$ 个数表示 $k=i-1$ 时的答案（$1≤i≤n+1$）。

简单样例

.in
4
1 1 2 3

.out
2 4 5 0 1

解释：存在 $12$ 个不同的排列对应上述答案，分别如下：

$k=0$：$(2,3,1,1)$ $(3,2,1,1)$

$k=1$：$(1,2,3,1)$ $(1,3,1,2)$ $(2,1,3,1)$ $(3,1,1,2)$

$k=2$：$(1,1,3,2)$ $(1,2,1,3)$ $(1,3,2,1)$ $(2,1,1,3)$ $(3,1,2,1)$

$k=3$：没有答案

$k=4$：$(1,1,2,3)$

---

希望有 高效 的算法；当然欢迎解答之前帖子的问题。