No.695 square1001 and Permutation 4
レベル : / 実行時間制限 : 1ケース 7.000秒 / メモリ制限
: 75 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 24
作問者 :
square1001
/ テスター :
e869120
タグ : / 解いたユーザー数 24
作問者 :
square1001
/ テスター :
e869120
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。