İnək#11177
Bessie öz sevimli otlağının ortasındakı böyük bir daşın üzərində həkk olunmuş sirli bir yazıya rast gəldi. Görünür ki, yazı yalnız üç simvoldan ibarət olan qədim, sirli bir dildə edilib: , və . Bessie bu mətni deşifrə edə bilməsə də, o, ardıcıl yazılmış , və hərflərinin onun sevimli sözünü əmələ gətirdiyini fərq etdi. İndi o, bu yazıda sözünün neçə dəfə rast gəlindiyini bilmək istəyir.
Bessie üçün hərfləri arasında başqa simvolların olması önəmli deyil — vacib olan yalnız , və hərflərinin düzgün ardıcıllıqla düzülməsidir. Bundan əlavə, sözünün müxtəlif təkrarları eyni hərflərdən istifadə edə bilər. Məsələn, sözü sətrində bir dəfə, sətrində iki dəfə və CCOOWW sətrində səkkiz dəfə rast gəlinir.
Verilmiş yazı mətninə əsasən, Bessie-yə sözünün orada altsıra (subsequence) kimi neçə dəfə rast gəlindiyini müəyyən etməkdə köməklik edin.
Birinci sətirdə bir tam ədəd verilir (n \le 10^5). İkinci sətirdə simvoldan ibarət bir sətir verilir, onların hər biri , və ya hərfidir.
Giriş sətrində sözünün altsıra kimi neçə dəfə rast gəlindiyini çıxarın, yəni hərflər ardıcıl yerləşməli deyil.
Diqqət edin ki, cavab çox böyük ola bilər, ona görə də hesablamalar üçün -bitlik tam ədədlərdən istifadə edilməlidir (məsələn, C++-da long~long və ya Java-da ).
Nümunə 1