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.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke 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).

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U prvi i jedini red izlazne datoteke upisati ostatak pri deljenju broja načina da progsice ostvare svoju zamisao brojem 1.000.000.007.

Primer 1.

5
patka

8

Objašnjenje.

Na slici su prikazane sve mogućnosti (prekrižene su one progsice koje treba da napuste arenu). Slika prikazuje pogled s istočne tribine, a uočava se da i publika sa zapadne vidi isti redosled boja. Primetiti da se ne ubraja mogućnost kada sve progsice napuste teren (tj., mora ostati bar jedna da nastavi zabavljanje publike).