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

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