問題一覧 > 教育的問題

No.3046 yukicoderの過去問

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 35
作問者 : maimai
2 ProblemId : 2744 / 出題時の順位表
問題文最終更新日: 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
入力
9
2
1 2
出力
55

No.786 京都大学の過去問 サンプル2と同じ意味を持つ入力です.

サンプル3
入力
11
4
2 4 6 8
出力
0
偶数段しか登れないので,ちょうど11段を登る組合せが存在しません.

サンプル4
入力
100000
4
1 2 4 8
出力
30131883

$1000000007$ で割った余りを出力してください.

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