B. Поло оцон шувуу ба байшингууд

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

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

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

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

Бяцхан оцон шувуу Поло өөрийн тосгондоо үнэхээр хайртай. Түүний тосгон нь $n$ ширхэг байшинтай ба 1-ээс $n$ хүртэл дугаарлагдсан байв. Байшин бүр нь бүхэл тоо агуулах модон самбартай ба $i$-дахь байшингийн модон самбар нь $p_{i}$ ($1 ≤ p_{i} ≤ n$) тоог агуулна.

Бяцхан оцон шувуу өөрийн тосгоны эргэн тойрноор алхах дуртай. Алхалт нь дараах байдлаар харагдана. Эхлээд тэрээр $x$ дугаартай байшин дээр зогсож байна. Дараа нь $x$ дугаартай байшингийн модон самбар дээр байх дугаартай байшин уруу алхах (өөрөөр хэлбэл $p_{x}$ дугаартай байшин) ба үүний дараа $p_{x}$ дугаартай байшингийн модон самбар дээр байх дугаартай байшин уруу алхана (өөрөөр хэлбэл $p_{p_{x}}$ дугаартай байшин) гэх мэтчилэн үргэлжлэх юм.

Бид дараах зүйлсийг мэдэж байгаа:

  1. Оцон шувуу 1-ээс $k$ хүртэлх дугаартай (эдгээр нь өөрсдөө орно) ямар ч байшингаас эхэлж алхсан 1 дугаартай байшинд очиж чадна.
  2. Оцон шувуу $k + 1$-ээс $n$ хүртэлх дугаартай (эдгээр нь өөрсдөө орно) ямар ч байшингаас эхэлж алхсан 1 дугаартай байшинд яасан ч очиж чадахгүй.
  3. Оцон шувуу 1 дугаартай байшингаас эхэлж алхвал тэрээр тэгээс ялгаатай тооны хэсэг алхалтын дараа уг байшиндаа эргэн ирж чадна.

Та дээрх 3-н нөхцөлийг хангаж байхаар байшингуудын модон самбар дээр дугаарууд бичих нийт боломжийн тоог олох юм. Уг тоог $1000000007$ $(10^{9} + 7)$-д хуваан үлдэгдлийг хэвлэнэ үү.

Оролт

Байшингуудын тоо $n$ болон бодлогын нөхцөл доторх $k$ тоог илэрхийлэх зайгаар тусгаарлагдсан 2 бүхэл тоо өгөгдөнө ($1 ≤ n ≤ 1000, 1 ≤ k ≤ min(8, n)$).

Гаралт

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

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

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

Оролт
5 2
Гаралт
54
Оролт
7 4
Гаралт
1728
Сэтгэгдлүүдийг ачааллаж байна...