D. Гимнастикийн хана

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

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

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

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

Манао барилгын компанид ажиллаж байна. Саяхан хүүхдийн паркд гимнастикийн хана байгуулах захиалга ирсэн. Манао компани хамгийн их мөнгө хэмнэж байхаар бүтээн байгуулалтын төлөвлөгөө байгуулахаар томидогдсон.

Гимнастикийн хананы тодорхойлолтыг үзсэнийхээ дараа Манао хэд хэдэн маргаантай шаардлагуудыг илрүүлсэн ба эдгээрийг компаны давуу тал гэж үзэхээр шийдсэн. Түүний эцсийн дизайныг дараах байдлаар тодорхойлж болно:

  • Хэд хэдэн урт танилцуулья. Байгууламжын төв нь $n$ урттай модон шон байна.
  • $1, 2, ..., n$ өндөр бүр дээр шон дээр бэхэлсэн хөндлөн мод байна. Хөндлөн мод бүр урьдчилан тодорхойлогдсон дөрвөн зүгийн аль нэгд нь бэхлэгдэнэ.
  • Хүүхэд нэг чиглэлд бэхлэгдсэн хоорондоо $h$-с ихгүй зайтай хоёр хөндлөн модны хооронд авирч чадна. Хэрвээ хүүхэд газар байвал $1$-с $h$ өндөртэй дурын хөндлөн модруу авирч чадна. Манаогийн байгууламжинд хүүхэд хэрвээ газраас эхлэн авирч байгаа бол $n - h + 1, n - h + 2, ..., n$ өндөрт байгаа хөндлөн моддын ядаж нэгэнд нь хүрч чаддаг байх ёстой.

Зүүн талын зурагт гимнастикийн хананы ерөнхий дүрсийг үзүүлсэн бол баруун талын зурагт Манаогийн байгууламжыг үзүүлсэн байна.

Манао түүний шаардлагуудад нийцэх хичнээн ялгаатай байгууламжын дизайн байх боломжтой вэ гэж гайхаж байна. Энэ тоо маш их гарч болох учир $1000000009 (10^{9} + 9)$ тоонд хуваагаад үлдэгдлийг хэвлэнэ үү. Хэрвээ хоёр дизайны $i$ өндөрт байгаа хөндлөн моднууд нь нэг зүгт бэхлэгдээгүй $i$ өндөр олдож байвал тухайн хоёр дизайныг ялгаатайд тооцно.

Оролт

Нэг мөрөнд зайгаар тусгаарласан хоёр бүхэл тоо $n$ ба $h$ ($1 ≤ n ≤ 1000$, $1 ≤ h ≤ min(n, 30)$) байна.

Гаралт

Нэг мөрөнд дизайнуудын тоог $1000000009 (10^{9} + 9)$ тоонд хуваагаад гарсан үлдэгдлийг хэвлэ.

Орчуулсан: Г.Мэндбаяр

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

Оролт
5 1
Гаралт
4
Оролт
4 2
Гаралт
148
Оролт
4 3
Гаралт
256
Оролт
5 2
Гаралт
376

Тэмдэглэл

$h = 2$ байх хэд хэдэн дизайныг авч үзье. Эхний хөндлөн мод нь $d_{1}$ чиглэлд хоёр дахь хөндлөн мод нь $d_{2}$ чиглэлд ($1 ≤ d_{i} ≤ 4$) гээд үргэлжилсэн дизайныг $d_{1}$$d_{2}$$...$$d_{n}$ тэмдэгт мөрөөр тэмдэглэнэ.

"1231" дизайн буюу эхний гурван хөндлөн мод нь ялгаатай зүгт бэхлэгдсэн харин сүүлийнх нь эхнийхтэй ижил зүгт бэхлэгдсэн дизайн. Хүүхэд 3 болон 4 өндөртэй хөндлөн моддын алинд нь ч хүрч чадахгүй.

"414141" дизайн. Хүүхэд 5 өндөртэй хөндлөн модонд хүрч чадна. Ингэхийн тулд тэр эхний хөндлөн модруу авирах ёстой ба тэгээд гурав дахь тэгээд тав дахь хөндлөн модруу авирах ёстой. Мөн тэр хоёр дахь, дөрөв дахь, зургаа дахь хөндлөн моддыг ашиглан 6 өндөртэй хөндлөн модонд хүрч чадна.

"123333" дизайн. Хүүхэд хоёроос дээш өндөртэй хөндлөн модонд хүрч чадахгүй.

"323323" дизайн. Эхний, гурав дахь, дөрөв дахь болон зургаа дахь хөндлөн модыг ашиглан 6 өндөрт гарч чадна.

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