Qatarın formalaşdırılması

Dəmir yolu daşımaları ilə məşğul olan bir şirkət, müəyyən sayda vaqondan ibarət qatar yaratmaq üçün sifariş alıb. Problem ondadır ki, şirkətin müxtəlif vaxtlarda istehsal olunmuş vaqonları var və hər bir vaqonun hər iki ucunda iki növ birləşmə növü ola bilər. Şirkətin həmçinin bir lokomotivi var.

Həm lokomotiv, həm də vaqonlar üçün birləşmələr $\text{A}$ və ya $\text{B}$ hərfi ilə göstərilib. Vaqonu və ya lokomotivi əks tərəfə çevirmək mümkün deyil.

Vaqonlar və lokomotiv haqqında məlumat verilib. Mövcud vaqon növlərindən verilmiş uzunluqda müxtəlif qatarlar formalaşdırmağın yollarının sayını tapmaq lazımdır. Əlavə tələb odur ki, formalaşdırılmış qatarın hər iki ucundakı birləşmə növü lokomotivin birləşmə növünə uyğun olmalıdır.

Qatarlar fərqli hesab olunur, əgər bir ucundan digərinə müqayisə edildikdə heç olmasa bir fərq aşkar edilərsə.

Misal 1. Tutaq ki, şirkətin $\text{AA}$, $\text{AA}$, $\text{AB}$, $\text{BA}$, $\text{BA}$ vaqonları və $\text{AB}$ lokomotivi var. Qatar $4$ vaqondan ibarət olmalıdır. Verilmiş vaqonlardan yalnız iki fərqli qatar formalaşdırmaq olar: $\text{BAAAABBA}$ və $\text{BAABBAAA}$. Lokomotivi qatarın həm sol tərəfinə (birləşmə $\text{B}$ istifadə edərək), həm də sağ tərəfinə (birləşmə $\text{A}$ istifadə edərək) qoşmaq olar.

Misal 2. Tutaq ki, şirkətin hər növdən yalnız bir vaqonu var ($\text{AA}$, $\text{AB}$, $\text{BA}$, $\text{BB}$) və $\text{AA}$ lokomotivi var, qatar üç vaqondan ibarət olmalıdır. Qatar formalaşdırmağın üç yolu var: $\text{AAABBA}$, $\text{ABBAAA}$ və $\text{ABBBBA}$.