Sehr

Verilən ardıcıllıqda neçə sehrli alt sıranın olduğunu hesablayan bir proqram yazın.

Giriş verilənləri

Birinci sətir $n(2\le n\le 10^5)$ tam ədədini ehtiva edir — cənab Daskalovun ardıcıllığındakı simvolların sayı. İkinci sətir $n$ ingilis hərflərindən ibarətdir. Hərflər həm böyük, həm də kiçik ola bilər. Qeyd edək ki, eyni hərfin böyük və kiçik formaları fərqli simvollar hesab olunur ($A$ və $a$ fərqli simvollardır).

Çıxış verilənləri

Verilən sətirdəki sehrli alt sətirlərin sayını çıxarın. Bu rəqəm böyük ola biləcəyi üçün, onu $10^9+7$-yə bölünən qalıq kimi çıxarın.

Nümunələr

1-ci test üçün izah. Sehrli alt sətirlər $abc,cba,abc$ və $abccba$ olacaq. Qeyd edək ki, $ab$ alt sətiri sehrli deyil, çünki $c$ hərfi orada yoxdur.

2-ci test üçün izah. Yalnız $abcABC$ alt sətiri sehrlidir (çünki $a$ və $A$ fərqli hərflərdir, biri kiçik, digəri böyük hərfdir).

3-cü test üçün izah. Sehrli sətirlərin sayı $22$-dir və onlardan biri $SwSwwS$-dir.