問題文

カンガルーのガンモ君は、一列に並んだ岩の端から端までジャンプして渡ろうとしています。

岩は$WK+1$個等間隔で一列に並んでおり、左から順に$0, 1, 2, \cdots\ , WK$と番号が付けられています。 番号が$W$の倍数の岩はすべて白く、ガンモ君は今岩$0$の上に着地しており、岩$WK$まで渡ろうとしています。

ガンモ君は、今いる岩から番号が$A_1, A_2, \cdots, A_N$大きい岩に渡ることができます。 これはつまり、岩$i$にいるとき、好きな整数$1\le j \le N$を選んでジャンプし、岩$i+A_j$の上に着地することができるということです。 番号の小さいほうに飛ぶことはできません。

ただし、ガンモ君は白い岩を$2$つ連続で飛び越すことはしないことにしました。 これはつまり、すべての整数$0\le i \lt K$について、岩$iW$に着地しないならば必ず岩$(i+1)W$に着地するということです。

以上の跳び方で、岩$0$から岩$WK$までジャンプする方法は何通りあるか、$10^9+7$で割った余りを求めてください。 ただし、ジャンプの方法が異なるとは、一方の方法で着地するがもう一方の方法で着地しないような岩が存在することをいいます。

入力

$N\ W\ K$
$A_1\ A_2\ \cdots\ A_N$

入力は以下の制約を満たします。

• 入力はすべて整数
• $1 \le W \le 40$
• $1 \le N \le 2W$
• $1 \le A_i \le 2W$
• $i\ne j$ならば$A_i \ne A_j$
• $1 \le K \le 10^{18}$

出力

ジャンプの方法の数を$10^9+7$で割った余りを出力し、最後に改行してください。

サンプル

2 4 1
1 2

5

2 5 1
1 2

8

5 40 31415926535
2 3 5 7 11

320973216