#00044D

Cheerleaders

Cica je vođa grupe progsica - čirlidersica koje su se specijalizovale za zabavljanje publike na Državnom takmičenju iz programiranja. Tokom poluvremena ove prestižne manifestacije progsice izvode svoj performans.
Svaka progsica obučena je u kostim određene boje. Cica i ekipa zamislile su da se, kao vrhunac nastupa, poređaju u liniju duž pravca sever-jug, a da potom neke od njih napuste arenu (moguće je i da nijedna ne ode) i to tako da publika sa istočne tribine, gledajući preostale progsice, vidi isti redosled boja kakav vidi i publika sa zapadne tribine. Tim povodom vas mole za pomoć: pitaju na koliko načina mogu ostvariti svoju zamisao.


InputU prvom redu nalazi se broj progsica, n (1 ≤ n ≤ 5.000). U drugom redu dat je poredak progsica, onako kako ih vidi publika s istočne tribine, u momentu kada neke od njih treba da napuste arenu. Poredak je dat u formi stringa dužine n, pri čemu i-ti karakter u stringu označava boju kostima i-te progsice (naravno, isti karakteri uvek označavaju istu boju, a različiti karakteri različitu).

OutputU prvi i jedini red upisati ostatak pri deljenju broja načina da progsice ostvare svoju zamisao brojem 1.000.000.007.


Input
5
patka

Output
8

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.