農夫 Fred 想要重新設計他房子的圍籬。Fred 的圍籬由 $n$ 塊高度各異的垂直木板組成。第 $i$ 塊木板的高度為 $h_i$ ($1 \le h_i \le n$)。最初，所有木板的高度皆不相同。

為了重新設計圍籬，Fred 會選擇某個連續的區段 $[l \dots r]$ 並將其「整平」，即透過切割木板，使該區段內所有木板的高度都等於該區段中的最小高度。更具體地說，該區段的新高度變為 $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$，對於所有 $l \le i \le r$ 皆成立。

請問 Fred 透過執行此程序若干次（可能為 0 次）後，總共能得到多少種不同的圍籬設計？由於答案可能非常大，請將結果對 $10^9 + 7$ 取模後輸出。

若兩種設計 $A$ 與 $B$ 中存在至少一塊木板的高度不同，則視為不同的設計。

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 3000$)，代表 Fred 圍籬的木板數量。 第二行包含 $n$ 個相異的整數 $h_i$ ($1 \le h_i \le n, 1 \le i \le n$)，代表每塊木板的高度。

輸出格式

輸出一個整數，代表可能獲得的不同圍籬設計數量，並對 $10^9 + 7$ 取模。

範例

輸入 1

3
1 3 2

輸出 1

4

輸入 2

5
1 2 3 4 5

輸出 2

42

輸入 3

7
1 4 2 5 3 6 7

輸出 3

124