問題

Sakky さんは $1$ から $N$ までの番号がついた $N$ 体のプラモデルを持っています．$i$ 番目のプラモデルの高さは $A_i$ です．
あなたは Sakky さんに $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ を $1$ つ与えます．
$P$ を受け取った Sakky さんは，番号が左から順に $P_1,P_2\dots,P_N$ となるように $N$ 体のプラモデルを横一列に並べます．
横一列に並べられたプラモデルの高さが，左から単調非減少になるような順列 $P$ は何通りあるでしょうか．

答えは非常に大きくなる可能性があるため，$10^9+7$ で割った余りを求めてください．

なお，プラモデルの高さが左から単調非減少になるような順列 $P$ とは，厳密には以下の条件を満たす $P$ のことを指します．

• すべての $i=1,2,\dots,N-1$ に対して $A_{P_i}\le A_{P_{i+1}}$ が成り立つ．

制約

• 入力はすべて整数
• $1\le N\le 2\times 10^5$
• $1\le A_i\le 10^{9}$

入力

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

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

出力

答えを整数で出力しなさい．

入出力例

4
1 2 2 3

2

$P=(1,2,3,4)$ と $P=(1,3,2,4)$ が条件を満たします．

5
1 1 1 1 1

120

すべての順列が条件を満たします．