E. Шидтэнүүд ба Бооцоо

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

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

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

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

Нэгэн улсад Шидтэнүүд амьдардаг байжээ. Тэд нэгэн сонин байдлаар бооцоо тавих дуртай байв.

2 шидтэн $n$ орой болон $m$ ирмэг бүхий нэгэн тогтмол бус чиглэлтэй граф зурав (тайлбар: тогтмол бус чиглэлтэй граф буюу acyclic directed graph гэдэг нь ямар ч чиглэлтэй циклүүд агуулаагүй байх хязгаарлагдмал тооны ирмэг болон орой агуулах чиглэлтэй граф юм. Илүү дэлгэрэнгүйг https://en.wikipedia.org/wiki/Directed_acyclic_graph-ээс уншина уу.) Энд графын оройнууд нь $1$-ээс $n$ хүртэл дугаарлагдсан байх юм. Эх гэдэг нь ямар ч орж буй ирмэггүй оройг хэлэх ба хонхор гэдэг нь ямар ч гарч буй ирмэггүй оройг хэлнэ. Ямар нэгэн орой нь нэгэн зэрэг хонхор болон эх орой байж болохыг анхаарна уу. Түүнчлэн шидтэнүүдийн уг граф доторх хонхор болон эх оройн тоонууд нь тэнцүү байх юм.

Шидтэнүүд эх оройнуудыг тэдгээрийн оройн дугааруудын ихсэх дарааллын дагуу $1$-ээс $k$ хүртэл дугаарлав. Мөн адил байдлаар хонхор оройнуудыг $1$-ээс $k$ хүртэл дугаарлав.

Бооцоо тавихын тулд шидтэнүүд нэгэн ид шид хэрэглэн бүх эх оройнуудаас бүх хонхор оройнууд хүртэлх $k$ ширхэг замуудын олонлог сонгох ба ингэхдээ ямар ч 2 замууд нь ижил оройнууд агуулаагүй байхаар сонгоно. Уг тохиолдолд хонхор орой бүрийн хувьд яг нэг эх оройгоос уг хонхор орой уруу хүрэх зам оршин байна. $i$-р хонхор оройн хувьд $a_{i}$-р эх оройгоос уг хонхор орой хүртэл зам оршин байна гэж тэмдэглэе. Хэрэв $i < j$ бөгөөд $a_{i} > a_{j}$ байвал бид уг $(i, j)$ хосыг урвуу гэж нэрлэнэ. Хэрэв урвуу хосуудын дундаас $(1 ≤ i < j ≤ k)$ байх бүх боломжит $(i, j)$ хосуудын тоо нь тэгш байвал эхний шидтэн ялах бөгөөд 2-дахь шидтэн нь түүнд нэг ширхэг шидэт зоос өгөх юм. Бусад тохиолдолд 2-дахь шидтэн ялах бөгөөд эхний шидтэнээс нэг ширхэг шидэт зоос авна.

Манай шидтэнүүдийн сэтгэл ихэд хөдөлсөн тул тэд дахин шинэ замуудыг сонгон тоглосоор байх бөгөөд бүх боломжит замуудын олонлогийг яг нэг нэг удаа сонгон тоглох юм. Ижил орой агуулаагүй байх замуудын 2 олонлогийн хувьд хэрэв нэг олонлог доторх ямар нэгэн зам дээр орших ирмэг нь нөгөө олонлог доторх ямар ч зам дээр нь оршин байхгүй байвал эдгээр 2 олонлогийг ялгаатай гэж үзнэ. Тэгвэл та тэдэнд туслан бүх боломжит замуудын олонлогийн хувьд эхний тоглогчийн ялах нийт ялалтын тоог $p$ модулаар бодон олж өгнө үү. Энд $p$ тоо нь анхны тоо байх юм.

Оролт

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

Дараагийн $m$ ширхэг мөрөнд графын ирмэгүүдийн тайлбар өгөгдөнө. Мөр болгонд зайгаар тусгаарлагдсан хос бүхэл тоо $a_{i} b_{i}$-ууд өгөгдөх ба эдгээр нь $a_{i}$ оройгоос $b_{i}$ орой хүртэл ирмэг оршин байгааг илэрхийлэх юм. Уг граф нь тогтмол бус чиглэлтэй граф байх бөгөөд ижил тооны эх орой болон хонхор орой агуулсан байна. Граф нь олон тооны ирмэг агуулсан байж болохыг анхаарна уу.

Гаралт

Бодлогын хариулт буюу эхний тоглогчийн нийт ялалтын тоог $p$ анхны тоон модулаар бодсон утгыг хэвлэнэ үү. Ялалтын тоо нь сөрөг тоо байж болох боловч модулын үлдэгдэл нь заавар сөрөг биш тоо байхыг анхаарна уу (жишээг харна уу).

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

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

Оролт
4 2 1000003
1 3
2 4
Гаралт
1
Оролт
4 2 1000003
4 1
3 2
Гаралт
1000002
Оролт
4 4 1000003
2 1
2 4
3 1
3 4
Гаралт
0
Оролт
6 5 1000003
1 4
1 5
1 6
2 6
3 6
Гаралт
0
Оролт
5 2 1000003
5 1
3 4
Гаралт
1

Тэмдэглэл

Эхний жишээнд яг нэг ширхэг замуудын олонлог оршин байна -- . Урвуу хосуудын тоо нь 0 буюу тэгш тоо учраас эхний шидтэн 1 зоос хожно.

2-дахь жишээнд яг нэг ширхэг замуудын олонлог оршин байна -- . Мөн түүнчлэн яг нэг ширхэг урвуу хос байх бөгөөд ингэснээр эхний шидтэн -1 зоос хожих юм .

3-дахь жишээнд нийтдээ 2 ширхэг замуудын олонлог байх бөгөөд эдгээрийн нэгэн дээр нь эхний шидтэн зоос алдах ба нөгөө олонлог дээр нь зоос хожих тул нийтдээ 0 зоос хожно.

4-дэх жишээнд ямар ч замуудын олонлог оршин байхгүй байна.

5-дахь жишээнд (2, 3, 5) гэсэн дугаартай оройнууд дээр байрлах 3-н эх орой, (1, 2, 4) гэсэн дугаартай оройнууд дээр байрлах 3-н хонхор орой байна. гэсэн нэгэн замуудын олонлог нь 2 ширхэг урвуу хос агуулах ба өөрөөр хэлбэл тэгш тооны хос агуулах юм.

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