D. Үнэг ба аялал

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

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

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

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

Сиел үнэг энэ зун Нью Фоксланд руу аялах гэж байна.

Нью Фоксланд $m$ ширхэг чиглэлгүй замаар холбогдсон $n$ үзвэртэй. Замаар холбогдсон $2$ үзвэрийг зэргэлдээ гэж нэрлэе. Сиел үнэг $k$ хоногийн турш уг хотоор аялах ба өдөрт яг нэг үзвэрээр зочлох болно.

Нью Фоксландад нэг чухал дүрэм байдаг: хэрэв тухайн үзвэрийн хувьд таны очиж үзээгүй нэгээс олон зэргэлдээ үзвэртэй бол та энэ үзвэрийг үзэх боломжгүй.

Эхлээд Сиел үнэг ямар ч үзвэрээр зочлоогүй байгаа гэж үзнэ. Тэр аль ч үзвэрээс өөр үзвэр лүү очих боломжтой. Өөрөөр хэлбэл $a$ үзвэрийг үзсэний дараа тэрээр Фоксландын дүрмийг хангасан өмнө нь очиж байгаагүй дурын $b$ үзвэр лүү очиж болно. Учир нь эдгээрийн хооронд зам байхгүй байсан ч эдгээр үзвэрийн хооронд завиар аялах боломжтой.

Тэр хичнээн ялгаатай аялалын төлөвлөгөө гаргаж чадахаа мэдэхийг хүсч байгаа. Сиел Нью Фоксландаар хичнээн өдөр аялахаа шийдэж чадахгүй байгаа учраас $0$-ээс $n$ хүртэлх $k$ бүхэл тоо бүрийн хувьд энэ тоог $10^{9} + 9$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ үү.

Оролт

Эхний мөр нь $n$, $m$ ($1 ≤ n ≤ 100, 0 ≤ m ≤ \frac{n(n-1)}{2}$) гэсэн хоёр бүхэл тоо агуулах ба эдгээр нь үзвэрийн тоо болон чиглэлгүй замын тоо юм.

Дараа нь $m$ мөрүүд байх бөгөөд мөр бүр нь замыг тодорхойлсон $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$ ба $a_{i} ≠ b_{i}$) бүхэл тоонуудыг агуулна. Аль ч хоёр үзвэрийг хамгийн ихдээ нэг замаар л холбоно.

Гаралт

$n + 1$ ширхэг бүхэл тоо буюу $0$-ээс $n$ хүртэлх бүх $k$ бүхэл тооны хувьд боломжит аяллын төлөвлөгөөний тоог $10^{9} + 9$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
3 2
1 2
2 3
Гаралт
1
2
4
4
Оролт
4 4
1 2
2 3
3 4
4 1
Гаралт
1
0
0
0
0
Оролт
12 11
2 3
4 7
4 5
5 6
4 6
6 12
5 12
5 8
8 9
10 8
11 9
Гаралт
1
6
31
135
483
1380
3060
5040
5040
0
0
0
0
Оролт
13 0
Гаралт
1
13
156
1716
17160
154440
1235520
8648640
51891840
259459200
37836791
113510373
227020746
227020746

Тэмдэглэл

Эхний жишээнд $k = 3$ учраас $4$ аяллын төлөвлөгөө байна: $(1, 2, 3), (1, 3, 2), (3, 1, 2), (3, 2, 1)$.

Хоёр дахь жишээнд Сиел эхний өдөр ямар ч үзвэрээр зочилж чадахгүй, тиймээс $k > 0$ үед хариулт нь $0$ байна.

Гурав дахь жишээнд Фоксланд дараах байдлаар харагдана:

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