K. 无聊的猪宝宝

无聊的猪宝宝有一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$。

它想将其划分成若干段，设为 $[l_1,r_1],[l_2,r_2],\cdots,[l_m,r_m]$（$m$ 自行决定），满足：

• $l_1=1$，$r_m=n$。对于任意整数 $i\in[1,m]$，$l_i\le r_i$，若 $i\ne m$ 则 $r_i+1=l_{i+1}$。
• 以下两个条件中至少有一个成立：
  • 条件 A：对于任意整数 $i\in[1,m]$，都有 $a_{l_i}\le a_{l_i+1}\le\cdots\le a_{r_i}$。
  • 条件 B：对于任意整数 $i\in[1,m]$，都有 $a_{l_i}\ge a_{l_i+1}\ge\cdots\ge a_{r_i}$。

求满足上述要求的划分方案的个数。答案对 $10^9+7$ 取模。

第一行一个整数 $n$（$1\le n\le 10^5$），表示序列的长度。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1\le a_i\le10^9$）。

一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例 1

输入

6
1 2 3 2 2 1

输出

14

解释

可以用两个集合的容斥原理来计算这个样例的答案。

把 $a_1,a_2,\cdots,a_6$ 划分成 $m$ 段，相当于从 $5$ 个邻项之间的间隙中选 $m-1$ 个插入隔板。

要使条件 A 成立，必须且只需在 $a_3$ 与 $a_4$ 之间、$a_5$ 与 $a_6$ 之间插入隔板，可得方案数为 $2^3=8$。

要使条件 B 成立，必须且只需在 $a_1$ 与 $a_2$ 之间、$a_2$ 与 $a_3$ 之间插入隔板，可得方案数为 $2^3=8$。

要使两者同时成立，同理可得方案数为 $2$。

所以，答案是 $8+8-2=14$。

样例 2

输入

12
1 1 2 3 2 2 1 9 1000000000 23 24 25

输出

284