有 $N$ 个村庄排成一排，编号为 $1$ 到 $N$。村庄 $1$ 是最左边的村庄，村庄 $N$ 是最右边的村庄。村庄的高度是介于 $1$ 到 $N$ 之间的互不相同的整数。

您希望将这些村庄划分为若干个连续段。每个段必须包含至少一个村庄，且每个村庄必须恰好属于一个段。如果两个村庄在同一个段中，那么它们之间的所有村庄也必须在同一个段中。

在每个段中，将在高度最高的村庄中建造一座信标塔。为了使信标塔之间能够高效地相互通信，建造了信标塔的村庄的高度从左到右必须形成一个严格递增的序列。

请计算满足上述约束条件的可能划分方案数。

输入格式

第一行包含一个整数 $N$，表示村庄的数量（$1 \le N \le 500\,000$）。

第二行包含 $N$ 个整数 $h_1, h_2, \dots, h_N$，表示村庄 $1, 2, \dots, N$ 的高度（$1 \le h_i \le N$）。所有的 $h_i$ 互不相同。

输出格式

输出满足上述约束条件的可能划分方案数。由于答案可能很大，请输出答案对 $10^9 + 7$ 取模后的结果。

样例

输入样例 1

5
1 4 2 5 3

输出样例 1

6

输入样例 2

3
3 2 1

输出样例 2

1

输入样例 3

8
6 3 1 7 2 5 4 8

输出样例 3

20