AT_past202109_n.ジグザグな数列

定义满足以下两个条件之一的序列 $b$ 为“之字形数列”：（记 $|b|$ 为 $b$ 的长度）

• $|b|\ge 2$，且对于所有 $1\le i\lt |b|$，若 $i$ 为奇数则 $b_i\lt b_{i+1}$，否则 $b_i\gt b_{i+1}$。

• $|b|\ge 2$，且对于所有 $1\le i\lt |b|$，若 $i$ 为奇数则 $b_i\gt b_{i+1}$，否则 $b_i\lt b_{i+1}$。

给定一个长为 $n$ 的数列 $a$。众所周知，$a$ 中（不一定连续）的非空子序列的个数为 $2^n-1$。请求出在所有这些子序列中，有多少个“之字形数列”？答案模 $(10^9+7)$。

共两行，第一行为一个整数 $n$，第二行为 $n$ 个整数，表示数列 $a$。

一行一个整数表示题目所求。

样例 #1 解释

所有长大于 $1$ 的子序列均满足条件。

样例 #2 解释

注意，即使两个子序列相同，但由于位置不同，我们还是要把它算两次。

数据规模与约定

$1\le n\le 2\times 10^5$，$1\le a_i\le 10^9$。