D. Олья ба граф

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

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

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

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

Олья-д $n$ орой болон $m$ ирмэгээс тогтох жингүй, чиглэлтэй граф байв. Бид ямар нэгэн байдлаар графын оройнууд нь 1-ээс $n$ хүртэл дугаарлагдсан гэж үзнэ. Мөн $v$ оройгоос $u$ орой хүртэлх графын ирмэг бүрийн хувьд дараах тэнцэтгэл биш биелнэ: $v < u$.

Одоо Олья дараах нөхцөлүүд биелж байхаар уг граф дээр дурын тооны (0 ч байх боломжтой) ирмэгүүдийг хэчнээн аргаар нэмж болохыг мэдэхийг хүсжээ:

  1. Та $i$ $(i < n)$ дугаартай ямар ч оройноос $i + 1, i + 2, ..., n$ дугаартай оройнууд уруу очиж болно.
  2. $v$ оройноос $u$ орой хүртэл явж буй графын ямар ч ирмэгийн хувьд дараах тэнцэтгэл биш биелнэ: $v < u$.
  3. Ямар ч 2 оройн хооронд хамгийн ихдээ 1 ирмэг байна.
  4. $j - i ≤ k$ нөхцөлийг хангах $i, j$ $(i < j)$ хос оройнуудын хоорондох хамгийн бага зай нь $j - i$ ирмэгтэй тэнцүү байна.
  5. $j - i > k$ нөхцөлийг хангах $i, j$ $(i < j)$ хос оройнуудын хоорондох хамгийн бага зай нь $j - i$ эсвэл $j - i - k$ ирмэгтэй тэнцүү байна.

Бид хэрэв эхний үр дүнгийн граф нь $i$-аас $j$ хүртэл ирмэгтэй ба 2-дахь үр дүнгийн граф нь ийм ирмэггүй байх $i, j$ $(i < j)$ хос оройнууд оршин байвал уг 2 аргыг ялгаатай гэж үзнэ.

Олья-д тусална уу. Нийт аргын тоо нь хэт их байж болох учраас хариуг $1000000007$ $(10^{9} + 7)$ модулаар бодож хэвлэнэ үү.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдсан 3-н бүхэл тоо $n, m, k$ $(2 ≤ n ≤ 10^{6}, 0 ≤ m ≤ 10^{5}, 1 ≤ k ≤ 10^{6})$ өгөгдөнө.

Дараагийн $m$ мөрөнд анхны графын ирмэгүүдийн тайлбар өгөгдөнө. $i$-дахь мөрөнд зайгаар тусгаарлагдсан хос бүхэл тоо $u_{i}, v_{i}$ $(1 ≤ u_{i} < v_{i} ≤ n)$ өгөгдөх ба эдгээр нь $u_{i}$-аас $v_{i}$ хүртэлх чиглэлтэй ирмэгээр холбогдож буй оройнуудын дугаарыг илэрхийлнэ.

Ямар ч хос $u_{i}, v_{i}$ оройнуудын хувьд эдгээрийн хооронд хамгийн ихдээ нэг ирмэг байх юм. Мөн графын ирмэгүүд нь $u_{i}$ нь үл буурах дарааллаар өгөгдөнө. Хэрэв $u_{i}$ оройгоос олон тооны ирмэг гарч байвал эдгээр ирмэгүүд нь $v_{i}$ нь өсөх дарааллаар өгөгдөнө.

Гаралт

Бодлогын хариултыг $1000000007$ $(10^{9} + 7)$ модулаар бодон хэвлэнэ үү.

Орчуулсан: Баатархүү

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

Оролт
7 8 2
1 2
2 3
3 4
3 6
4 5
4 7
5 6
6 7
Гаралт
2
Оролт
7 0 2
Гаралт
12
Оролт
7 2 1
1 3
3 5
Гаралт
0

Тэмдэглэл

Эхний жишээнд нийт 2 арга байна: Эхний арга нь юу ч нэмэхгүй байх бөгөөд 2-дахь арга нь $2$-р оройноос $5$-р орой хүртэл нэг ирмэг нэмэх юм.

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