CF367E Sereja and Intervals

Sereja 对区间很感兴趣，所以他为你准备了一个关于区间的问题。一个区间定义为一对整数 $[l, r]$，其中 $1 \leq l \leq r \leq m$。如果满足条件 $l_2 \leq l_1 \leq r_1 \leq r_2$，则区间 $[l_1, r_1]$ 属于区间 $[l_2, r_2]$。 Sereja 想在纸上写出一个包含 $n$ 个区间的序列 $[l_1, r_1]$，$[l_2, r_2]$，…，$[l_n, r_n]$。同时，序列中任意一个区间都不能属于同一序列中的另一个区间。此外，Sereja 非常喜欢数字 $x$，他希望序列中至少有一个区间满足 $l_i = x$。Sereja 想知道，有多少种不同的方式可以写出这样的区间序列？ 请你帮助 Sereja，求满足要求的方案数，对 $1000000007$ 取模。 如果存在某个 $j$ $(1 \leq j \leq n)$，使得两组序列中第 $j$ 个区间不同，则认为这两种方式不同。

第一行包含三个整数 $n$、$m$、$x$ $(1 \leq n \cdot m \leq 100000, 1 \leq x \leq m)$ —— 区间序列的数量 $n$，区间取值的上界 $m$ 和 Sereja 最喜欢的数字 $x$。

输出一个整数，为满足条件的序列个数，对 $1000000007$ 取模。

在第三个样例中，以下序列均为合法方案：$[1, 1], [3, 3]$，$[1, 2], [3, 3]$，$[2, 2], [3, 3]$，$[3, 3], [1, 1]$，$[3, 3], [2, 2]$，$[3, 3], [1, 2]$。 由 ChatGPT 5 翻译