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 A və ya 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 AA, AA, AB, BA, BA vaqonları və AB lokomotivi var. Qatar 4 vaqondan ibarət olmalıdır. Verilmiş vaqonlardan yalnız iki fərqli qatar formalaşdırmaq olar: BAAAABBA və BAABBAAA. Lokomotivi qatarın həm sol tərəfinə (birləşmə B istifadə edərək), həm də sağ tərəfinə (birləşmə A istifadə edərək) qoşmaq olar.
Misal 2. Tutaq ki, şirkətin hər növdən yalnız bir vaqonu var (AA, AB, BA, BB) və AA lokomotivi var, qatar üç vaqondan ibarət olmalıdır. Qatar formalaşdırmağın üç yolu var: AAABBA, ABBAAA və ABBBBA.
Giriş verilənləri
Birinci sətirdə boşluqla ayrılmış N - şirkətin sərəncamında olan vaqonların sayı və K - qatarın vaqonlarla tələb olunan uzunluğu verilir. İkinci sətir lokomotivin birləşmə növünü təsvir edir. Növbəti N sətir vaqonların birləşmə növlərini təsvir edir. Təsvirlər AB, AA, BB və ya BA kimi verilib.
1 ≤ K ≤ N ≤ 40.
Çıxış verilənləri
Birinci sətirdə heç olmasa bir qatar formalaşdırmaq mümkündürsə, "YES" sözü, əks halda "NO" sözü çıxarılır.
Əgər qatar formalaşdırmaq mümkündürsə, ikinci sətirdə bunu etməyin yollarının sayı göstərilməlidir.