Paiza 君の階段登り 2 Python2編（paizaランク A 相当）

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

Paiza 君は段数が N の階段を上りきる必要があります。
今、Paiza 君は階段の 0 段目にいてこの階段の N 段目まで上ろうとしています。
長さ M の数列 a_1, a_2, ..., a_M が与えられます。
Paiza 君は上る先の段が存在するなら階段を一度に a_i (1 ≦ i ≦ M) 段上ることが出来ます。
N 段目までの上り方は何通りありますか。
ただし、答えは非常に大きい数となることがあるので 10^10 で割ったあまりを出力してください。

入力される値

N M
a_1 a_2 ... a_M

・1 行目では階段の段数 N と数列の長さ M が与えられます。
・2 行目では数列の値 a_1, a_2, ..., a_M が空白区切りで与えられます。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 答えを 1 行で出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。

条件: すべてのテストケースにおいて, 以下の条件をみたします

・入力はすべて整数
・1 ≦ N ≦ 10^6
・1 ≦ M ≦ 5
・a_1 = 1 < a_2 < ... < a_M ≦ 100

入力例1: 10 1
1

出力例1: 1

入力例2: 5 2
1 2

出力例2: 8

入力例3: 8 4
1 2 4 10

出力例3: 55

問題一覧へ戻る