Şarı Buma

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ı $3$ 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 $W$ rəngli topu seçir və onu altıncı topdan sonra, yəni iki $W$-nin soluna yerləşdirir. Balf bu topu yerləşdirdikdən sonra, $W$ rəngli toplar silinir, çünki bu seqmentin uzunluğu $3$ olur, nəticədə sıra $AAABBBBB$ olur. İndi $B$ rəngli toplar silinir, çünki $B$ rəngli topların seqmenti uzunluğu $5$-ə çatır. Beləliklə, sıra $AAA$ 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.

Giriş verilənləri

İ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.

Çıxış verilənləri

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ələr