Given a sequence A₁ , A₂ , A₃ .. A_N of length N . Find total number of wave subsequences having length greater than 1.
Wave subsequence of sequence A₁ , A₂ , A₃ .. A_N is defined as a set of integers i₁ , i₂ .. i_k such that A_i1 < A_i2 > A_i3 < A_i4 .... or A_i1 > A_i2 < A_i3 > A_i4 .... and i₁ < i₂ < ...< i_k.Two subsequences i₁ , i₂ .. i_k and j₁ , j₂ .. j_m are considered different if k != m or there exists some index l such that i_l ! = j_l

INPUT:
First line of input consists of integer N denoting total length of sequence.Next line consists of N integers A₁ , A₂ , A₃ .. A_N .

OUTPUT:
Output total number of wave subsequences of given sequence . Since answer can be large, output it modulo 10⁹+7

CONSTRAINTS:
1 ≤ N ≤ 10⁵
1 ≤ A_i ≤ 10⁵