AT_maximum_cup_2023_e 小大小大……

$ (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) $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ p_1 $ $ p_2 $ $ \ldots $ $ p_N $

答えを出力せよ。

### Sample Explanation 1 $ 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 $ 個です。 ### Constraints - $ 1 \leq N \leq 3 \times 10^5 $ - $ 1 \leq p_i \leq N $ - $ i \neq j $ ならば $ p_i \neq p_j $ - 入力はすべて整数