配点 : $1300$ 点

ストーリー

今度こそ、僕たちは敵を倒した。帰る途中、僕はあることを思い出していた。

世界の裏側には、この世界の基盤の以外にも基盤があった。それらは完全に壊れていて、すでに滅びてしまったのかもしれない。もしかしたら、その世界でも今回のようなことがあって、新しい基盤と世界が作られていったのかもしれない、だとしたら───僕たちはその連鎖を食い止めたんだ。

そんなことを考えていると、後ろからいろはちゃんの声がした。
「せーんぱい！」

問題文

$N$ つの世界が左右一列に並んでいます。
それぞれの世界は「自然さ」という固有の値を持っており、左から$p_1,p_2,..,p_N$の順番に、$1$ から $N$ を並べ替えた数列をなしています。
この数列は、$N$ のみを要素とする長さ $1$ の列をはじめとして、「項をひとつ選んで、その右隣にそれより小さな値を挿入する」という操作の繰り返しによって生まれたことがわかっています。
与えられる数列の生まれる方法が何通り考えられるか求め、$10^9+7$ で割った余りを求めてください。
ただし二つの”数列の生まれる方法”が異なるとは、ある $1$ 以上 $N-1$ 以下の整数 $k$ が存在して、$k$ 回目の操作で選択した項と挿入した値の少なくともどちらか一方が異なることを意味します。

制約

• 入力はすべて整数
• $1 \\leq N \\leq 2\\times 10^5$
• $p_1 = N$
• $p_1,p_2,...,p_N$ は $\\{1,...,N\\}$ の順列

入力

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

$N$ $p_1$ $p_2$ ... $p_N$

出力

答えを出力してください。

入力例 1

4
4 2 3 1

出力例 1

3

この順列を生み出す操作の方法は以下に示した列の変化を実現する$3$通りです。
・${4}→{4,3}→{4,2,3}→{4,2,3,1}$
・${4}→{4,3}→{4,3,1}→{4,2,3,1}$
・${4}→{4,1}→{4,3,1}→{4,2,3,1}$

入力例 2

4
4 3 2 1

出力例 2

6

入力例 3

7
7 6 3 4 1 2 5

出力例 3

36

入力例 4

30
30 4 26 15 21 19 14 8 12 7 16 20 2 5 25 13 3 23 18 29 10 27 1 28 9 6 11 24 22 17

出力例 4

321470237

解説

解説