No.997 Jumping Kangaroo

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 75
作問者 : ganmodokixganmodokix / テスター : monkukui2monkukui2
10 ProblemId : 3559 / 出題時の順位表
問題文最終更新日: 2020-02-22 00:25:32

問題文

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

岩は$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$で割った余りを出力し、最後に改行してください。

サンプル

サンプル1
入力
2 4 1
1 2
出力
5

ジャンプの方法は、
$0 \to 1 \to 2 \to 3 \to 4$
$0 \to 2 \to 3 \to 4$
$0 \to 1 \to 3 \to 4$
$0 \to 1 \to 2 \to 4$
$0 \to 2 \to 4$
の5通りです。

サンプル2
入力
2 5 1
1 2
出力
8

サンプル3
入力
5 40 31415926535
2 3 5 7 11
出力
320973216

出力が$10^9+7$で割った余りであることに注意してください。

提出するには、Twitter または、GitHubもしくは右上の雲マークをクリックしてアカウントを作成してください。