ACM İCPC-də ağır vəziyyət

Hüseyn, İbrahim və Ələkbər ACM ICPC müsabiqəsində iştirak edirlər. Onlar növbəti problemi həll etməyə çalışırlar:

Sizin əlifba hərflərindən və sual işarələrindən ibarət bir sətriniz var. İstənilən sual işarəsinin yerinə istənilən əlifba hərfini qoya bilərsiniz. Yalnız bir simvoldan ibarət neçə alt sətir ola biləcəyini sayın. ADA universitetinin komandasına bu problemi həll etməyə kömək edin.

Giriş

Bir sətrdən ibarətdir, uzunluğu 10^6-dan çox deyil. Sətir kiçik latın hərflərindən və sual işarələrindən ibarətdir.

Çıxış

Bu məsələnin cavabını çap edin.

İzah

Birinci nümunə üçün yalnız bir simvoldan ibarət ola biləcək alt sətirlər bunlardır: [1,1], [2,2], [3,3], [4,4], [2,3], [3,4].