Zadanie

Leremiáš a Miško

Počet bodov: 90

Táto úloha je rovnaká ako úloha zenit23ck2j

Raz sa malý Miško zúčastnil slovného hádania so svojimi kamarátmi. Všetci sedeli okolo stola a snažili sa uhádnuť tajné heslo. Keď prišla Miškova poradová chvíla, bol nervózny (pochopiteľne). No namiesto toho, aby povedal nejaké slovo, začal koktať a vypúšťať nahodilé hlásky.

“Kááá… ééeeé… ešte… mmmm… ťťť…,” koktal Miško beznádejne.

“Kemť?” opýtal sa neveriacky Leremiáš. Všetci sa zasmiali a za bruchá pochytali, pretože kemť nebolo ani zďaleka správne heslo. No Miško sa nevzdal a pokračoval v hádaní nahodilých písmen.

“Možno by bolo lepšie, keby si len hádal slová, Miško,” povedal mu jeden z kamarátov s úsmevom. “Tvoja mama,” odpovedal Miško s úsmevom a pokračoval v hádaní.

Úloha

Miško postupne hovorí nahodilé písmená z abecedy až kým súvisle nevysloví celé heslo. Miško vyslovuje písmená nezávisle a rovnomerne náhodne. Aký je očakávaný počet písmen, ktoré Miško vysloví, kým sa mu konečne podarí vysloviť celé heslo?

Vstup a Výstup

Prvý riadok vstupu obsahuje číslo \(A\), ktoré označuje veľkosť abecedy, z ktorej Miško vyslovuje písmená.

Na druhom riadku je heslo \(H\), pozostávajúce iba z prvých \(A\) malých písmen anglickej abecedy.

Vypíšte jedno desatinné číslo, ktoré označuje očakávaný počet vyslovených písmen, ktoré Miško vysloví, kým nepovie súvisle heslo \(H\).

Keďže počet písmen môže byť veľmi veľký, vypíšte ho modulo \(10^9 + 7\) (teda celočíselnú časť zmodulujte a desatinnú nechajte tak). Odpovede sú považované za správne, ak je ich absolútna alebo relatívna chyba nanajvýš \(10^{-6}\).

Príklad

Input:

2
aaa

Output:

14.0

Input:

2
abb

Output:

8.0

Input:

3
abbc

Output:

81.0