У Пети есть последовательность целых чисел a1, a2, ..., an. Петя хочет, чтобы все числа в ней были равны h. Он умеет выполнять операцию «прибавления единицы на отрезке [l, r]»: прибавить ко всем элементам последовательности с номерами от l до r (включительно) единицу. При этом Петя никогда не выбирает какое-то число в качестве начала отрезка повторно. Аналогично, Петя никогда не выбирает какое-то число в качестве конца отрезка повторно. Другими словами, для любых двух отрезков [l1, r1] и [l2, r2], на которых Петя выполнял прибавление единицы, верны следующие неравенства: l1 ≠ l2 и r1 ≠ r2.
Сколько существует различных способов сделать все числа последовательности равными h? Выведите это количество способов по модулю 1000000007 (109 + 7). Два способа считаются различными, если в одном из них есть отрезок, которого нет в другом.
Выходные данные
Выведите единственное целое число — ответ на задачу по модулю 1000000007 (109 + 7).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
1 1 1
|
4
|
|
2
|
5 1
1 1 1 1 1
|
1
|
|
3
|
4 3
3 2 1 1
|
0
|