No.71 音楽ゲーム

時間制限:$2.0sec$ / メモリ制限:$256MB$ / tester:ei1333

問題文

olphe君は大人気音楽ゲームで遊んでいる。
このゲームではすべての楽曲が常にハイスコア順にソートされる。(ただし、ハイスコアが同じ場合は先にそのスコアを出した楽曲の方がスコアが高いとみなされる)
olphe君は次のルールに従ってゲームをプレイする。

  1. $1$回目は一番ハイスコアの低い曲をプレイする。
  2. $1$回目以外は前回プレイした曲よりもハイスコアの高い曲の中で、一番ハイスコアの低い曲をプレイする。(ここでは並べ替え後のハイスコアを参照する)
  3. 楽曲の選択ができなかったらolphe君はプレイをやめる。

なお、全ての楽曲の理論値は$10^9$である。
$N$曲のハイスコア情報が与えられたときにolphe君のプレイの仕方が何通りあるか求めよ。
ただし、答えは非常に大きくなる可能性があるため、$10^9+7$で割った余りを出力せよ。

制約

  • $1≦N≦10^5$
  • $0≦a_i≦10^5$

入力形式

入力は以下の形式で標準入力から与えられる。 


N
a_1 a_2 … a_N

出力

プレイの仕方の通り数を10^9+7で割った余りを出力してください。

入出力例

入力1 

3
1 2 2
出力1 

3

(追記) 1 -> (終わり) , 1 -> (2または3) -> (3または2) -> (終わり) , 1 -> (2または3) -> (終わり) の3通りのプレイの仕方があります。

入力2 

3
1 2 3
出力2 

4