No.8046 yukicoderの過去問
問題文最終更新日: 2021-03-06 18:16:46
note
これは yukicoder April fool contest 2019 の問題として作問されました．
問題文
$K$ 段の階段があります．
赳也君なら1,2,3段，
Y君なら1,2段ずつ登れるかもしれませんが，
舞葉君ならば，1歩で $x_1, x_2,\ldots,x_N$ 段のいずれかで階段を昇ることができます．
このとき，舞葉君がちょうど $K$ 段の階段を昇る昇り方は何通りあるか．
ただし，解はとても大きくなるので，$1000000007$ で割った余りを出力してください．
入力
$K$ $N$ $x_1\ x_2\ \ldots\ x_N$
$1 \le K \le 10^5$
$1 \le N \le 10^5$
$1 \le x_i \le 10^5$
$x_i < x_{i+1}$
すべて整数．10進数表記である．
出力
最後に改行してください。
サンプル
サンプル1
入力
4 2 1 3
出力
3
次の3通りです．「3段,3段」は4段を超えるので解に含まれません．
- 1段,1段,1段,1段
- 1段,3段
- 3段,1段
サンプル2
サンプル3
入力
11 4 2 4 6 8
出力
0偶数段しか登れないので，ちょうど11段を登る組合せが存在しません．
サンプル4
入力
100000 4 1 2 4 8
出力
30131883
$1000000007$ で割った余りを出力してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。