Олья-д $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$-р орой хүртэл нэг ирмэг нэмэх юм.