配点: $1300$ 点

ストーリー

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

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

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

问题描述

有 $N$ 个世界排成一行。
每个世界都有固有的"自然度"值，按照 $1$ 到 $N$ 的顺序从左到右排列，记为 $p_1,p_2,..,p_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

解说

解説