当前没有测试数据。

题目描述

瓜瓜在设计游戏关卡。游戏共有 $n$ 关，只能顺次尝试。第 $i$ 关有 $a_i$ 种通关方法，每过一关就可以得到一个徽章；或者选择放弃，跳到下一关但没有徽章。

如果完全通关两个玩家存在一关通过方法不同，那么称他们有不同的游戏路径。

现在瓜瓜设计好了 $\{a_i\}$ 的值，他想知道分别获得 $x(0 \leqslant x \leqslant n)$ 个徽章时，所有可能的游戏路径有多少条。

因为答案可能很大，请对 $p$ 取模。

输入描述

第一行有两个整数 $n, p$，其中 $1 \leqslant n \leqslant 5000, 1 \leqslant p \leqslant 10^9 + 7$。

第二行有 $n$ 个整数，分别为 $a_1, a_2, \cdots a_n$，其中 $1 \leqslant a_i \leqslant p - 1$。

输出描述

在一行输出 $n+1$ 个整数，分别表示得到 $x$ 个徽章时，可能的路径条数。

样例

5 998244353
1 2 3 4 5

1 15 85 225 274 120

提示

对于样例，路径条数是 $[1, 15, 85, 225, 274, 120]$。