ADA tələbələri - Hüseyn, İbrahim və Ələkbər ACM İCPC-də iştirak edir. Onlar aşağıdakı məsələni həll etməyə çalışır: Kiçik latın hərfləri və sual işarəsindən ibarət string verilir. Hər bir sual işarəsinin yerinə istənilən hərfi yazmaq olar. Eyni hərflərdən ibarət olan stringə yaxşı string deyilir. Bu stingin neçə alt stringi yaxşı ola bilər? Qeyd: s1s2 ... sn stringinin alt stringi (1 ≤ l ≤ r ≤ n ) şərtini ödəyən hər hansı slsl+1 ...sr stringidir. ADA universitetinin komandası özlərini çox pis hiss edir (deyəsən COVID-19a yoluxublar). Bu məsələni həll etməkdə onlara kömək edin.

Giriş:

Girişdə yeganə sətirdə uzunluğu 106 -dan çox olmayan s stringi verilir. String kiçik latın hərfləri və sual işarəsindən ibarət ola bilər.

Çıxış:

Tələb olunan sayı çap edin.