Codeforces Round #804 (Div. 2)
4 өдрийн дараа |
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]}$.