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