列の消去 5 Python2編（paizaランク S 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A = a_1, a_2, ..., a_N が与えられます。
数列 A に対して次の操作を行います。
・操作: 操作時点で A の最も左にある数を A_L とし、1 ≦ x ≦ A_L となる任意の整数 x を選ぶ。
その後、左から x 個の連続する要素を削除する。ただし、A の現在の要素が x 個に満たない場合は削除できない。
操作を任意の回数おこない、数列の長さを 0 にできるような操作手順は何通りあるかを求めてください。
ただし、操作手順の数が非常に大きな数になることがあるので 10^10 で割った余りを出力してください。
- 入力される値
-
N
a_1 a_2 ... a_N
・1 行目では数列の長さ N が与えられます。
・2 行目では数列の値 a_1, a_2, ..., a_N が半角空白区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
答えを 1 行で出力してください。末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて, 以下の条件をみたします
・入力はすべて整数
・1 ≦ N ≦ 10^6
・1 ≦ a_i ≦ 10^6 (1 ≦ i ≦ N)
- 入力例1
-
3
3 2 1
- 出力例1
-
4
- 入力例2
-
5
1 1 1 1 1
- 出力例2
-
1
- 入力例3
-
35
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
- 出力例3
-
7179869184
