g6-08063. 义卖摊三问 未做

义卖摊准备了 $n$ 种面额的兑换券，第 $i$ 种面额 $a_i$ 元，每种券都有很多张。摊主想用它们表示 $0$ 到 $N$ 元的价格牌，只看每种券各用了几张、不看摆放顺序。请你帮摊主算三件事：第一，$0,1,\dots ,N$ 每个金额各有多少种凑法；第二，如果把这些券排成一排、摆放顺序不同也算不同，凑出 $N$ 元有多少种排法；第三，金额不超过 $N$ 元的凑法一共有多少种。所有结果都要对 $10^9+7$ 取模。

第一行两个整数 $n$、$N$。

第二行 $n$ 个整数 $a_i$。

共三行：

• 第一行：$N+1$ 个整数，用空格分隔，第 $w+1$ 个表示恰好凑出 $w$ 面值的组合方案数；
• 第二行：一个整数，表示恰好凑出 $N$ 面值的排列方案数；
• 第三行：一个整数，表示不超过 $N$ 面值的组合方案总数。

所有结果均对 $10^9+7$ 取模。

输入 1

3 5
1 2 5

输出 1

1 1 2 2 3 4
9
13

从 $0$ 元到 $5$ 元的凑法数依次是 $1,1,2,2,3,4$，其中 $5$ 元的 $4$ 种是 $1\times 5$、$2+1+1+1$、$2+2+1$、$5$；把顺序也区分时 $5$ 元有 $9$ 种排法；金额不超过 $5$ 元的凑法数总共 $1+1+2+2+3+4=13$。

$1\le n\le 100$，$1\le N\le 2\times 10^4$，$1\le a_i\le 2\times 10^4$，保证面值互不相同。