問題文

$N$ 要素からなる整数列 $A=(A_1,A_2,\cdots ,A_N)$ が与えられます。
$A$ の最長増加部分列の取り出し方の総数を求めてください。
取り出した部分列が列として等しい場合でも、選んだ位置の集合が異なれば別の取り出し方として数えます。

すなわち、$1\le I_1<I_2<\cdots <I_M\le N$ かつ $A_{I_1}<A_{I_2}<\cdots <A_{I_M}$ となるような整数列 $I$ のうち、要素数 $M$ が最大になるようなものが何通りあるかを求めてください。

ただし、答えを ${10}^9+7$ で割った余りを出力してください。

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

入力は以下の制約を満たします。

• $N,A_i$ は整数である
• $1\le N\le 2\times {10}^5$
• $-{10}^9\le A_i\le {10}^9$

出力

$A$ の最長増加部分列の取り出し方の総数を ${10}^9+7$ で割った余りを出力してください。

サンプル

5
1 4 2 5 3

3

3
1 1 2

2

12
1 1 2 2 3 1 2 4 3 3 4 4

40