← 返回题目列表

Codeforces · 367/E

E. Sereja 和间隔

中文机器翻译题面 查看原题

Sereja 对数字的区间很感兴趣,所以他为你准备了一个关于区间的问题。数字区间是一对整数 [l, r] (1 ≤ l ≤ r ≤ m)。如果满足以下条件,则区间 [l1, r1] 属于区间 [l2, r2]:l2 ≤ l1 ≤ r1 ≤ r2。

Sereja 想要在一张纸上写出 n 个区间 [l1, r1], [l2, r2], ..., [ln, rn] 的序列。此时,序列中的任何区间都不能属于序列中的某个其他区间。另外,Sereja 非常喜欢数字 x,他希望序列中的某个(至少一个)间隔具有 li = x。 Sereja 想知道,有多少种不同的方式来书写这样的音程?

帮助 Sereja 找到所需的模 1000000007 (109 + 7) 的路数。

如果存在这样的 j (1 ≤ j ≤ n),即两个对应序列中的第 j 个间隔不相等,则两种方式被认为是不同的。

输入

第一行包含整数 n、m、x (1 ≤ n·m ≤ 100000, 1 ≤ x ≤ m) — 序列中的段数、段中数字的约束以及 Sereja 最喜欢的数字。

输出

在一行中打印答案模 1000000007 (109 + 7)。

示例

输入 #1

1 1 1

输出 #1

1

输入 #2

3 5 1

输出 #2

240

输入 #3

2 3 3

输出 #3

6

注意

在第三个示例中,下一个序列将是正确的:{[1, 1], [3, 3]}, {[1, 2], [3, 3]}, {[2, 2], [3, 3]}, {[3, 3], [1, 1]}, {[3, 3], [2, 2]}, {[3, 3], [1, 2]}。