305D орчуулах · Codeforces.mn

# Олья ба граф
Олья-д $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)$ модулаар бодон хэвлэнэ үү.

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

-- Баатархүү

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

Оролт

Гаралт

Оролт

7 0 2

Гаралт

Оролт

7 2 1
1 3
3 5