問題一覧 > 通常問題

No.695 square1001 and Permutation 4

レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限 : 75 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : square1001square1001 / テスター : e869120e869120
3 ProblemId : 2231 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-11-12 16:39:54

お知らせ

  • 2020. 11. 12 : 最近のコンパイラのアップデートにより、JAVA のバージョンが出題当時 (2018. 6. 8) と変わったため、メモリ制限を 64 MB から 75 MB に変更いたしました。ご了承ください。

問題文

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

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