Сережа интересуется отрезками чисел, поэтому он приготовил для вас задачу про отрезки. Отрезок чисел — это пара целых чисел [l, r] (1 ≤ l ≤ r ≤ m). Отрезок [l₁, r₁] принадлежит отрезку [l₂, r₂], если выполняется условие: l₂ ≤ l₁ ≤ r₁ ≤ r₂.

Сережа хочет записать на листке последовательность из n отрезков [l₁, r₁], [l₂, r₂], ..., [l_n, r_n]. Причем никакой отрезок в последовательности не должен принадлежать какому-то другому отрезку в последовательности. А еще Сережа очень любит число x, поэтому он хочет, что бы хотя бы один из отрезков имел левую границу l_i = x. Сережу интересует вопрос: сколько существует различных способов записать такие отрезки?

Помогите Сереже, найдите описанное количество способов по модулю 1000000007 (10⁹ + 7).

Два способа считаются различными, если найдется такое j (1 ≤ j ≤ n), что j-ые отрезки в двух соответствующих последовательностях не равны.