E. Серёжа ба интервал

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Серёжа интервалд дуртай тул үүнтэй холбоотой бодлогыг танд бэлджээ. Тоон интервал нь [$l, r$] ($1 ≤ l ≤ r ≤ m$) хос тоо юм. Хэрвээ $l_2 ≤ l_1 ≤ r_1 ≤ r_2$ нөхцөл биелэж байвал [$l_2, r_2$] интервалд [$l_1, r_1$] интервал агуулагдана гэж үз.

Серёжа нэг нь ч нөгөөдөө агуулагддаггүй байхаар [$l_1, r_1$], [$l_2, r_2$], ... , [$l_n, r_n$] интервал бичихийг хүсэж байгаа. Мөн тэр $x$ тоонд маш дуртай тул ядаж нэг интервалын $l_i = x$ байх ёстой. Түүнд дээрх шаардлагыг хангахаар хэдэн янзаар интервалуудыг бичиж болохыг олж өгөөрэй.

Хариуг $1000000007$ ($10^9 + 7$)-д хуваасны үлдэгдлийг олно.

Хэрвээ 2 хариунд $j$-р интервалууд нь хоорондоо ялгаатай байх $j$ ($1 ≤ j ≤ n$) олддог бол ялгаатай хариу гэж үзнэ.

Оролт

Нэг мөрөнд интервалын тоо $n$, тооны хязгаар $m$, Серёжагийн дуртай тоо $x$ ($1 ≤ n·m ≤ 100000$, $1 ≤x ≤ m$) өгөгдөнө.

Гаралт

Хариуг $1000000007$ ($10^9 + 7$)-д хуваасны үлдэгдлийг хэвлэ.

Орчуулсан: zoloogg

Жишээ тэстүүд

Оролт
1 1 1
Гаралт
1
Оролт
3 5 1
Гаралт
240
Оролт
2 3 3
Гаралт
6

Тэмдэглэл

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]}$.

Сэтгэгдлүүдийг ачааллаж байна...