Фермер Фред хочет изменить дизайн забора своего дома. Забор Фреда состоит из $n$ вертикальных деревянных досок различной высоты. Высота $i$-й доски равна $h_i$ ($1 \le h_i \le n$). Изначально все высоты различны.

Чтобы изменить дизайн забора, Фред выбирает некоторый непрерывный отрезок $[l \dots r]$ досок и «выравнивает» их, подрезая так, чтобы все высоты на этом отрезке стали равны минимальной высоте на этом отрезке. Более конкретно, новые высоты досок на отрезке становятся равны $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$ для всех $l \le i \le r$.

Сколько различных дизайнов может получить Фред, применяя эту процедуру несколько (возможно, 0) раз? Поскольку ответ может быть очень большим, выведите его по модулю $10^9 + 7$.

Два дизайна $A$ и $B$ считаются различными, если существует хотя бы одна доска, высота которой в дизайне $A$ отличается от высоты в дизайне $B$.

Входные данные

Первая строка входных данных содержит $n$ ($1 \le n \le 3000$) — количество досок в заборе Фреда.

Вторая строка содержит $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