時間制限:$2.0sec$ / メモリ制限:$256MB$ / tester:ei1333
olphe君は大人気音楽ゲームで遊んでいる。
このゲームではすべての楽曲が常にハイスコア順にソートされる。(ただし、ハイスコアが同じ場合は先にそのスコアを出した楽曲の方がスコアが高いとみなされる)
olphe君は次のルールに従ってゲームをプレイする。
なお、全ての楽曲の理論値は$10^9$である。
$N$曲のハイスコア情報が与えられたときにolphe君のプレイの仕方が何通りあるか求めよ。
ただし、答えは非常に大きくなる可能性があるため、$10^9+7$で割った余りを出力せよ。
入力は以下の形式で標準入力から与えられる。
N
a_1 a_2 … a_N
プレイの仕方の通り数を10^9+7で割った余りを出力してください。
3
1 2 2
3
(追記) 1 -> (終わり) , 1 -> (2または3) -> (3または2) -> (終わり) , 1 -> (2または3) -> (終わり) の3通りのプレイの仕方があります。
3
1 2 3
4