問題文

(1,2,\ldots,N) の順列 P=(p_1,p_2,\ldots,p_N) が与えられます。

P を 1 個以上の空でない連続部分列 X_1,X_2,\ldots,X_K に分割し、以下のように (m_1,m_2,\ldots,m_K) を定めました。

• i が奇数ならば m_i は X_i に含まれる値の最小値
• i が偶数ならば m_i は X_i に含まれる値の最大値

(m_1,m_2,\ldots,m_K) としてあり得るものの個数を (10^9+7) で割った余りを求めてください。

制約

• 1 \leq N \leq 3 \times 10^5
• 1 \leq p_i \leq N
• i \neq j ならば p_i \neq p_j
• 入力はすべて整数

入力例 1

3
1 2 3

出力例 1

3

P を分割する方法は 4 通りあり、それぞれに対応する (m_1,m_2,\ldots,m_K) は以下の通りです。

• (1,2,3) に分割する。\min(1,2,3)= 1 なので対応する数列は (1) である。
• (1), (2,3) に分割する。\min(1)= 1, \max(2,3)=3 なので対応する数列は (1,3) である。
• (1,2),(3) に分割する。\min(1,2)= 1, \max(3) = 3 なので対応する数列は (1, 3) である。
• (1),(2),(3) に分割する。\min(1)= 1, \max(2)=2, \min(3)=3 なので対応する数列は (1,2,3) である。

以上より、 (m_1,m_2,\ldots,m_K) としてあり得るものは (1), (1,3), (1,2,3) の 3 個です。

入力例 2

5
5 4 1 3 2

出力例 2

15