K. Bored Piglet
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bored piglet has an integer sequence $$$a_1,a_2,\cdots,a_n$$$.

He wants to partition this sequence into several intervals, denoted as $$$[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$$$ (the value of $$$m$$$ is chosen arbitrarily), satisfying all of the following conditions:

  • $$$l_1=1$$$, $$$r_m=n$$$.
  • For every integer $$$i\in[1,m]$$$, $$$l_i\le r_i$$$; if $$$i\ne m$$$ then $$$r_i+1=l_{i+1}$$$.
  • At least one of the following two conditions holds:
    • Condition A: for every integer $$$i\in[1,m]$$$, $$$a_{l_i}\le a_{l_i+1}\le\cdots\le a_{r_i}$$$.
    • Condition B: for every integer $$$i\in[1,m]$$$, $$$a_{l_i}\ge a_{l_i+1}\ge\cdots\ge a_{r_i}$$$.
Compute the number of partitions that satisfy the above requirements. Print the answer modulo $$$10^9+7$$$.
Input

The first line contains a single integer $$$n$$$ ($$$1\le n\le10^5$$$).

The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$ ($$$1\le a_i\le10^9$$$).

Output

Print a single integer, the number of valid partitions modulo $$$10^9+7$$$.

Examples
Input
6
1 2 3 2 2 1
Output
14
Input
12
1 1 2 3 2 2 1 9 1000000000 23 24 25
Output
284
Note

We can use the inclusion-exclusion principle on two sets to calculate the answer of the first example:

Partitioning $$$a_1,a_2,\cdots,a_6$$$ into $$$m$$$ intervals is equivalent to choosing $$$m-1$$$ gaps among the $$$5$$$ gaps between adjacent elements and inserting separators there.

To make Condition A hold, it is necessary and sufficient to insert separators between $$$a_3$$$ and $$$a_4$$$, $$$a_5$$$ and $$$a_6$$$; thus the number of such partitions is $$$2^3=8$$$.

To make Condition B hold, it is necessary and sufficient to insert separators between $$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$; thus the number of such partitions is $$$2^3=8$$$.

To make both Condition A and Condition B hold, similarly we can obtain that the number of such partitions is $$$2$$$.

So, the answer is $$$8+8-2=14$$$.