農夫のフレッドは、自宅の柵を再設計したいと考えている。フレッドの柵は、様々な高さの $n$ 本の垂直な木の板で構成されている。$i$ 番目の板の高さは $h_i$ ($1 \le h_i \le n$) である。当初、すべての高さは相異なっている。

柵を再設計するために、フレッドは板の連続する区間 $[l \dots r]$ を選び、その区間内の最小の高さに合わせて板を切り揃えることで「平坦化」を行う。より具体的には、その区間内のすべての $i$ ($l \le i \le r$) について、新しい高さは $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$ となる。

この操作を数回（0回でもよい）適用することで、フレッドはいくつの異なる柵のデザインを得ることができるだろうか。答えは非常に大きくなる可能性があるため、$10^9 + 7$ で割った余りを出力せよ。

2つのデザイン $A$ と $B$ は、ある板の高さが $A$ と $B$ で異なるとき、異なるとみなす。

入力

入力の最初の行には、フレッドの柵の板の数 $n$ ($1 \le n \le 3000$) が含まれる。 2行目には、$n$ 個の相異なる整数 $h_i$ ($1 \le h_i \le n, 1 \le i \le n$) が含まれ、各板の高さを表す。

出力

得られる可能性のある異なる柵のデザインの数を、$10^9 + 7$ で割った余りで1つの整数として出力せよ。

入出力例

入力 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