Şarı Buma#9581
Balf yeni bir oyun öyrənir, adı Buma. Bu oyunda ona rəngli toplardan ibarət bir sıra verilir. Onun vəzifəsi, yeni bir topun rəngini və yerləşdiriləcəyi yeri seçməkdir (iki top arasında, bütün topların solunda və ya sağında).
Top yerləşdirildikdən sonra, aşağıdakı proses təkrarlanır: əgər yeni hərəkət nəticəsində eyni rəngli toplardan ibarət bir seqment yaranarsa və bu seqmentin uzunluğu ən azı olarsa, həmin seqmentdəki bütün toplar silinir.
Məsələn, AAABBBWWBB toplar sırasını nəzərdən keçirək. Tutaq ki, Balf rəngli topu seçir və onu altıncı topdan sonra, yəni iki -nin soluna yerləşdirir. Balf bu topu yerləşdirdikdən sonra, rəngli toplar silinir, çünki bu seqmentin uzunluğu olur, nəticədə sıra AAABBBBB olur. İndi rəngli toplar silinir, çünki rəngli topların seqmenti uzunluğu -ə çatır. Beləliklə, sıra olur. Lakin indi heç bir top silinmir, çünki uzanan seqment yoxdur.
Balf'a bütün topları siləcək yeni topun rəngini və yerləşdirilmə yerini seçmək üçün mümkün yolların sayını tapmağa kömək edin.
İngilis əlifbasının böyük hərflərindən ibarət, uzunluğu 3 \cdot 10^5-dən çox olmayan boş olmayan bir sətir verilir. Hər bir hərf müvafiq rəngli topu təmsil edir.
Bütün topları məhv edəcək yeni topun rəngini və yerləşdirilmə yerini seçmək üçün yolların sayını çıxarın.
Nümunə 1
Nümunə 2
Nümunə 3
Nümunə 4
Nümunə 5