C. Цагаан, хар бас цагаан

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

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

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

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

Поликарпус түүний амьдрал: "эхлээд цагаан судал тэгээд нэг хар тэгээд дахиад нэг цагаан" гэх тодорхойлолтод тохирч байна гэдэгт итгэлтэй байна. Мөн Поликарпус энэ дүрэм дараагийн $n$ өдөрт үйлчилнэ гэдэгт ч итгэж байна. Поликарпус өөрийгөө $w$ сайн үйл явдал болон $b$ сайн биш үйл явдлын дунд байна гэдгийг мэдэж байна. Өдөр бүр ядаж нэг үйл явдал тохионо. Өдөр бүр цагаан эсвэл хар судлын нэг хэсэг байх ба өдөр бүр ижил төрлийн үйл явдлууд тохиолдоно (сайн эсвэл сайн биш) гэсэн үг.

Хэрвээ Поликарпус цагаан судал (зөвхөн сайн үйл явдлууд тохиох судал, судлын урт нь ядаж нэг өдөр), хар судал (зөвхөн сайн биш явдлууд тохиох судал, судлын урт ядаж нэг өдөр), дахиад цагаан судал (зөвхөн сайн үйл явдлууд тохиох судал, судлын урт нь ядаж нэг өдөр) дээр байсан бол дараагийн $n$ өдөр ийм маягаар үргэлжлэх ялгаатай боломжийн тоо хэд вэ. $n$ өдрийн өдөр тус бүр гурван судлын аль нэгэнд нь л хамаарагдана.

Ижил төрлийн үйл явдлууд нэг нэгээсээ ялгаатай ч зарим үйл явдлууд ижил өдөр тохиосон ч тэд ямар нэг дарааллаар явагдана (зэрэгцээ үйл явдал болохгүй).

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

Оролт

Оролтын нэг мөрөнд $n$, $w$ ба $b$ ($3 ≤ n ≤ 4000$, $2 ≤ w ≤ 4000$, $1 ≤ b ≤ 4000$) бүхэл тоон утгууд байх буюу өдрүүдийн тоо, сайн болон сайн биш үйл явдлуудын тоо байна. $w + b ≥ n$ тодорхой.

Гаралт

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

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

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

Оролт
3 2 1
Гаралт
2
Оролт
4 2 2
Гаралт
4
Оролт
3 2 2
Гаралт
4

Тэмдэглэл

Бид сайн үйл явдлуудыг 1-с эхлэн тоонуудаар тэмдэглэх ба сайн биш үйл явдлуудыг '$a$'-с эхлэн үсгүүдээр тэмдэглэнэ. Босоо шулуунууд өдрүүдийг тусгаарлана.

Эхний жишээн дээр боломжит замууд нь: "$1|a|2$" ба "$2|a|1$". Хоёр дахь жишээн дээр боломжит замууд нь: "$1|a|b|2$", "$2|a|b|1$", "$1|b|a|2$" ба "$2|b|a|1$". Харин гурав дахь жишээн дээр боломжит замууд нь "$1|ab|2$", "$2|ab|1$", "$1|ba|2$" ба "$2|ba|1$" байна.

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