Sereja and Intervals
题目链接
题目翻译
有 个区间，你需要为每个区间分配左右端点，端点属于 。你需要保证区间两两互不包含且至少存在一个区间的左端点等于 ，输出方案数对 取模的结果，区间有标号。，。
Description
Sereja is interested in intervals of numbers, so he has prepared a problem about intervals for you. An interval of numbers is a pair of integers [l, r] (1 ≤ l ≤ r ≤ m). Interval [l1, r1] belongs to interval [l2, r2] if the following condition is met: l2 ≤ l1 ≤ r1 ≤ r2.
Sereja wants to write out a sequence of n intervals [l1, r1], [l2, r2], ..., [ln, rn] on a piece of paper. At that, no interval in the sequence can belong to some other interval of the sequence. Also, Sereja loves number x very much and he wants some (at least one) interval in the sequence to have li = x. Sereja wonders, how many distinct ways to write such intervals are there?
Help Sereja and find the required number of ways modulo 1000000007 (109 + 7).
Two ways are considered distinct if there is such j (1 ≤ j ≤ n), that the j-th intervals in two corresponding sequences are not equal.
The first line contains integers n, m, x (1 ≤ n·m ≤ 100000, 1 ≤ x ≤ m) — the number of segments in the sequence, the constraints on the numbers in segments and Sereja's favourite number.
In a single line print the answer modulo 1000000007 (109 + 7).
Input
The first line contains integers n, m, x (1 ≤ n·m ≤ 100000, 1 ≤ x ≤ m) — the number of segments in the sequence, the constraints on the numbers in segments and Sereja's favourite number.
Output
In a single line print the answer modulo 1000000007 (109 + 7).
Samples
1 1 1
1
3 5 1
240
2 3 3
6
Note
In third example next sequences will be correct: {[1, 1], [3, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[3, 3], [1, 1]}, {[3, 3], [2, 2]}, {[3, 3], [1, 2]}.