Sehr

Giriş

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