BoB004-E: Sorted Permutation

2 secs 1024 MB
kyaneko999's icon kyaneko999

問題

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

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

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

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

制約

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

入力

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

NN
A1  A2    ANA_1\;A_2\;\cdots\;A_N

出力

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

入出力例

入力例1
4
1 2 2 3
出力例1
2

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

入力例2
5
1 1 1 1 1
出力例2
120

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

Submit


Go (1.21)