G： ほぼ無限グリコ - Almost Infinite Glico

問題

N 個のマスが円環状に並んでいるフィールドがあります。 i 番目 (1 \leq i \leq N-1) のマスの 1 つ先は、 i+1 番目のマスになります。ただし、 i = N の場合、その 1 つ先は 1 番目のマスになります。

あなたが最初にいるマスは 1 番目のマスです。そこから以下のルールに従って、じゃんけんを K 回続けて行います。このとき、あなたと相手は特殊なじゃんけんを会得しているので、じゃんけんの勝ち方が M 通りあります。

• 相手とじゃんけんを行い、あなたが相手に勝ったとき、今出した手、すなわち勝ち方 i に応じたマス数 p_i だけ進みます。負けたときはその場に留まります。

K 回のじゃんけんを終えたあとに、あなたが i 番目のマスにいる場合の数を 1,000,000,007 で割った余りを、それぞれのマスについて求めてください。ここで 2 つの場合が異なるとは、 K 回のじゃんけんの各回のうち負けた回が一度でも異なる、または勝ち方が異なる回が一度でも存在することを言います。勝ち方も区別することに注意してください。また、それぞれの勝ち方について、発生する可能性が全くないものは存在しないこととします。

入力形式

入力は 1 + M 行与えられる。

N M K
p_1
...
p_M

1 行目では、マスの数 N 、 じゃんけんの勝ち方の数 M 、 じゃんけんを行う回数 K が与えられる。 続いて M 行与えられる。 i+1 行目では、 i 番目の勝ち方をした時に進めるマスの数 p_i が与えられる。

制約

• 1 \leq N \leq 8 \times 10^2
• 1 \leq M \leq 10^4
• 1 \leq K \leq 10^9
• 1 \leq p_i \leq 10^9

出力形式

出力は N 行からなる。

i 行目では、 K 回のじゃんけんを終えたあとにあなたが i 番目のマスにいる場合の数を出力せよ。

入力例1

10 3 2
3
6
6

出力例1

1
0
4
2
0
0
5
0
0
4

一般的なグリコです。この入力において、じゃんけんは 2 回行われます。

例えば、 2 回じゃんけんをした後に 1 番目のマスにいるためには、全てのじゃんけんで負けなければいけません。これ以外に 1 番目のマスで終わる組み合わせは存在しないため、 1 通りです。

2 回じゃんけんをした後に 4 番目のマスにいるためには、

• 1 回目のじゃんけんで 1 番目の勝ち方で勝つ → 2 回目のじゃんけんで負ける
• 1 回目のじゃんけんで負ける → 2 回目のじゃんけんで 1 番目の勝ち方で勝つ

の 2 通りがあります。順番が異なるならば、異なる場合として扱われることに注意してください。

入力例2

5 1 103
4

出力例2

355272559
885073297
355272559
607675915
607675915

1,000,000,007 で割った余りを出力することに注意してください。

Note

Link

 

---