Note

TLとMLの制約にご注意ください。
一部の(多数の?)言語ではAC不能かもしれません。
writer解はC++(ACL利用)で2600ms、Cで適当に書いて9200ms、tester解はC++(ACL不使用)で6200msです。
参考：配列のサイズと型を入力すると何MBか教えてくれるうし

問題文

$N$ 個の正整数 $A_1,\ldots,A_N$ と正整数 $M,C$ が与えられます。$s=1,2,\ldots,\sum_{i=1}^{N}A_i$ のそれぞれについて次の問題に答えてください。

$A_1,\ldots,A_N$ から $C$ 個選んで和を $s$ にする方法は何通りあるか、$\bmod M$ で求めてください。
より厳密には、$|\{I\subset \{1,\ldots,N\} \mid |I|=C \land \sum_{i\in I}A_i=s\}| \bmod M$ を求めてください。

入力

$N$ $M$ $C$
$A_1$ $\ldots$ $A_N$

$1\leq N\leq 90$
$2\leq M\leq 10^9$
$1\leq C\leq N$
$1\leq \sum_{i=1}^{N}A_i\leq 10^5$
$1\leq A_i$
入力は全て整数

出力

各 $s=1,2,\ldots,\sum_{i=1}^{N}A_i$ に対する答えを、この順に空白区切りで出力せよ。

サンプル

4 10 2
4 3 2 1

0 0 1 1 2 1 1 0 0 0

10 4 5
1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0