Сережа интересуется отрезками чисел, поэтому он приготовил для вас задачу про отрезки. Отрезок чисел — это пара целых чисел [l, r] (1 ≤ l ≤ r ≤ m). Отрезок [l1, r1] принадлежит отрезку [l2, r2], если выполняется условие: l2 ≤ l1 ≤ r1 ≤ r2.
Сережа хочет записать на листке последовательность из n отрезков [l1, r1], [l2, r2], ..., [ln, rn]. Причем никакой отрезок в последовательности не должен принадлежать какому-то другому отрезку в последовательности. А еще Сережа очень любит число x, поэтому он хочет, что бы хотя бы один из отрезков имел левую границу li = x. Сережу интересует вопрос: сколько существует различных способов записать такие отрезки?
Помогите Сереже, найдите описанное количество способов по модулю 1000000007 (109 + 7).
Два способа считаются различными, если найдется такое j (1 ≤ j ≤ n), что j-ые отрезки в двух соответствующих последовательностях не равны.
Выходные данные
В единственную строку выведите ответ по модулю 1000000007 (109 + 7).
Примечание
В третьем примере подходят следующие последовательности отрезков: {[1, 1], [3, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[3, 3], [1, 1]}, {[3, 3], [2, 2]}, {[3, 3], [1, 2]}.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1 1
|
1
|
|
2
|
3 5 1
|
240
|
|
3
|
2 3 3
|
6
|