Muallif: Обид Синдаров
Temurning grafi
Kichik Temurda g'aroyib graf bor. Bu graf quyidagi tartibda quriladi:
- Dastlab $k$ ta cho'qqidan iborat to'la graf (k-klika) olinadi (ya'ni barcha $k$ ta cho'qqi bir-biri bilan bog'langan).
- So'ngra grafga birma-bir yangi cho'qqilar qo'shiladi. Har bir yangi cho'qqi grafdagi mavjud bo'lgan va o'zaro klika hosil qiluvchi $k$ ta cho'qqi bilan bog'lanadi.
Temur ushbu grafda nechta har xil yoyilma daraxt (spanning tree) mavjudligini bilmoqchi. Graf cho'qqilari juda ko'p bo'lishi mumkinligi sababli, javobni $10^9 + 7$ moduli bo'yicha hisoblang.
Kiruvchi ma'lumotlar
Birinchi satrda ikkita butun son $n$ va $k$ beriladi ($1 \le n \le 10,000$, $1 \le k \le \min(n, 5)$) — grafdagi jami cho'qqilar soni va boshlang'ich klika o'lchami.
Keyingi $n-k$ ta satrning har birida $k$ tadan butun son — yangi qo'shilayotgan cho'qqi bog'lanadigan mavjud cho'qqilar raqamlari beriladi.
Chiquvchi ma'lumotlar
Misollar
| # | Input TXT | Output TXT |
|---|---|---|
| 1 |
3 2 1 2 |
3 |
| 2 |
4 3 1 2 3 |
16 |
Izoh
Birinchi misolda graf uchun quyidagi $3$ xil yoyilma daraxtni shakllantirish mumkin:
- $(1-2)$ va $(1-3)$ qirralarini qoldirish ($3-2$ qirrasini olib tashlash).
- $(1-2)$ va $(2-3)$ qirralarini qoldirish ($3-1$ qirrasini olib tashlash).
- $(1-3)$ va $(2-3)$ qirralarini qoldirish ($1-2$ qirrasini olib tashlash).
Jami har xil yoyilma daraxtlar soni $3$ ta.
Ikkinchi misolda $n=4, k=3$ bo'lganda, graf 4 ta cho'qqili to'la grafga ($K_4$) aylanadi. Keyli teoremasiga ko'ra, $n$ ta cho'qqili to'la grafning yoyilma daraxtlari soni $n^{n-2}$ formula bilan topiladi.
$4^{4-2} = 4^2 = 16$
Shuning uchun javob $16$ chiqadi.