No.695 square1001 and Permutation 4

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 64 MB / 通常問題
タグ : / 解いたユーザー数 13
作問者 : square1001square1001 / テスター : e869120e869120
2 ProblemId : 2231 / 出題時の順位表

問題文

Wait, where is "permutation"? - Just imagine it :)

$1 \times n$ のチェスボードがあります. マス $i$ を, 左から $i$ 番目のマスとします.
チェスの駒がマス $1$ にあります. チェスの駒がマス $i$ にあるとき, square1001 はマス $i+x_1, i+x_2, \cdots, i+x_m$ のいずれかに動かすことができます.
最終的にチェスの駒がマス $n$ に置かれるような動かし方の場合の数を求めてください.
ただし, 答えは非常に大きくなる可能性があるので、$100 \ 000 \ 000 \ 000 \ 000 \ 007$ で割ったあまりを求めてください.

入力

$n$ $m$
$x_1 \ x_2 \ \cdots \ x_m$

出力

$a_n$ を $100 \ 000 \ 000 \ 000 \ 000 \ 007$ で割ったあまりを $1$ 行で出力してください.
最後に改行してください.

制約

  • $2 \leq n \leq 20 \ 000 \ 000$.
  • $1 \leq m \leq 5$.
  • $1 \leq x_i \leq n-1 \ (1 \leq i \leq m)$.
  • $x_1, x_2, \dots, x_m$ はすべて異なる.

サンプル

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

次の $5$ 通りの動かし方があります.

  • マス $1$ --> マス $2$ --> マス $3$ --> マス $4$ --> マス $5$
  • マス $1$ --> マス $2$ --> マス $3$ --> マス $5$
  • マス $1$ --> マス $2$ --> マス $4$ --> マス $5$
  • マス $1$ --> マス $3$ --> マス $4$ --> マス $5$
  • マス $1$ --> マス $3$ --> マス $5$

サンプル2
入力
1000000 5
3 14 159 2653 58979
出力
73305885902670558

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。