Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
B. Автобусууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 265 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Нусгай Жералд гэрээсээ хол орших нэгэн сургуульд явдаг. Тиймээс тэр өдөр болгон автобусанд суух шаардлагатай байдаг. Гэрээс сургууль хүрэх зам шулуун хэрчимээр дүрслэгдэх ба уг шулуун яг $n + 1$ ширхэг автобусны буудлуудыг агуулна. Автобусны буудлууд Жералдын гэрээс эхлэн 0-ээс $n$ хүртэл дугаарлагдсан. Жералдын гэрийн буудал 0, сургуулийнх нь буудал n-ээр дугаарлагдсан.
Гэр, сургуулийн хооронд $m$ ширхэг автобус явдаг: $i$ дахь автобус $s_i$ буудлаас эхлэн $t_i (s_i < t_i)$ буудал хүртэл шулууны дагуух бүх буудлаар дайран явдаг. Жералд тэнэг биш болохоор суусан автобусаас сургууль аль болох ойр очиж буудаг (мэдээжээр замд нь буух ямар ч ашиггүй). Өөрөөр хэлбэл Жералд $i$ дахь автобуст $s_i$-аас $t_i - 1$ хүртэлх буудлуудаас суун зөвхөн $t_i$ буудал дээр бууна гэсэн үг.
Жералд буудлуудын хооронд алхаж чадахгүй мөн сургуулиас гэр чиглэлд хөдлөхгүй.
Жералд гэрээс сургууль хүртэл хэдэн ялгаатай зам байгааг мэдэхийг хүссэн тул түүнд тоог хэл. Хэрэв Жералд буудлуудын хоорондох зарим хэсэгт өөр өөр автобусаар өнгөрсөн бол замыг өөр гэж үзнэ. Замуудын тоо маш олон байж болох тул уг тоог $1000000007 (10^9 + 7)$-д хувааж гаргана.
Оролт
Эхний мөр зайгаар тусгаарлагдсан хоёр бүхэл тоог агуулна: $n, m (1 <= n <= 10^9, 0 <= m <= 10^5)$. Дараагийн $m$ мөр болгон $s_i, t_i$ хос тоонуудыг агуулна. Эдгээр нь автобуснуудын эхлэл болон төгсгөлийн зогсоолууд юм $(0 <= s_i < t_i <= n)$.
Гаралт
Зөвхөн сургууль хүрэх замын тоог $1000000007 (10^9 + 7)$-д үлдэгдэлтэй хуваан хэвлэнэ.
Орчуулсан: devman
Жишээ тэстүүд
Оролт
2 2 0 1 1 2
Гаралт
1
Оролт
3 2 0 1 1 2
Гаралт
0
Оролт
5 5 0 1 0 2 0 3 0 4 0 5
Гаралт
16
Тэмдэглэл
Эхний тесд сургууль хүрэх ганц л замын агуулна: Эхлээд нэг дүгээр автобусанд гарч нэг дүгээр буудал хүрээд хоёр дугаар автобуст суун хоёр дугаар буудал хүрнэ.
Хоёр дугаар тестэд сургуулийн байрлах 3 дугаар буудалд ямар автобуст очихгүй тул зөв хариулт 0.
Гурав дугаар тестэд сургуульд ойртож очихын тулд эхний 4 автобусыг авах эсвэл авахгүй байж болно. Тиймээс хариу нь $2^4 = 16$.