G. Бяцхан Артем ба Граф

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

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

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

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

Бяцхан Артем-д дараах байдлаар үүсэх нэгэн граф өгөгджээ: уг граф-ыг үүсгэхдээ эхлээд $k$ ширхэг оройнуудаас тогтох хэсэг бүлэг оройнууд дээр шинэ оройнуудыг нэг нэгээр нь нэмэх байдлаар үүсгэх юм.

Артем уг граф дахь дамнасан модны (spanning tree) тоог $10^{9} + 7$ модулаар бодон олохыг хүсжээ. Дамнасан мод гэдэг нь тухайн граф дахь бүх оройг агуулах модыг хэлнэ.

Оролт

Эхний мөрөнд 2 бүхэл тоо $n$ болон $k$ ($1 ≤ n ≤ 10 000$, $1 ≤ k ≤ min(n, 5)$) өгөгдөх ба эдгээр нь харгалзан графын нийт хэмжээ (оройнуудын тоо) болон анхны бүлэг оройнуудын оройн тоог илэрхийлнэ.

Дараагийн $n - k$ мөрөнд $k + 1$-дэх, $k + 2$-дахь, ..., $i$-дахь, ..., $n$-дэх оройнууд нь уг оройтой холбогдож буй $k$ ширхэг ялгаатай оройнуудын индексүүд болох $1 ≤ a_{ij} < i$-уудаар өгөгдөнө. Түүнчлэн эдгээр $k$ ширхэг ялгаатай оройнууд нь графын эхлэл болох бүлэг оройнуудыг үүсгэнэ.

Гаралт

Өгөгдсөн граф дахь дамнасан модны (spanning tree) тоог $10^{9} + 7$ модулаар бодсон хариу болох ганц бүхэл тоог хэвлэнэ үү.

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

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

Оролт
3 2
1 2
Гаралт
3
Оролт
4 3
1 2 3
Гаралт
16
Сэтгэгдлүүдийг ачааллаж байна...