Problem Statement

You are given an integer sequence $A=(A_1,A_2,\cdots,A_N)$ consisting of $N$ elements.
Find the total number of ways to take a longest increasing subsequence of $A$.
Even if the extracted subsequences are equal as sequences, they are counted as different ways if the sets of chosen positions differ.

In other words, among the integer sequences $I$ satisfying $1\le I_1\lt I_2\lt\cdots\lt I_M\le N$ and $A_{I_1}\lt A_{I_2}\lt\cdots\lt A_{I_M}$, find the number of those whose number of elements $M$ is maximum.

Output the answer modulo $10^9+7$.

Input

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

The input satisfies the following constraints.

• $N,A_i$ are integers
• $1\le N\le2\times 10^5$
• $-10^9\le A_i\le10^9$

Output

Output the total number of ways to take a longest increasing subsequence of $A$, modulo $10^9+7$.

Sample

5
1 4 2 5 3

3

3
1 1 2

2

12
1 1 2 2 3 1 2 4 3 3 4 4

40