Mucca#11177
La mucca Bessie si è imbattuta in una misteriosa iscrizione scolpita su un grande sasso in mezzo al suo prato preferito. Sembra che l'iscrizione sia scritta in un antico e misterioso linguaggio, il cui alfabeto è composto da soltanto tre simboli: , e . Sebbene Bessie non sia in grado di decifrare questo testo, ha notato che , e , scritti in sequenza, formano la sua parola preferita. Ora si chiede quante volte la parola compaia in questa iscrizione.
A Bessie non importa se tra le lettere di compaiono altri simboli — l'importante è che le lettere , e si presentino nell'ordine corretto. Inoltre, occorrenze diverse di possono utilizzare le stesse lettere. Per esempio, compare una volta nella stringa , due volte in e otto volte in CCOOWW.
Data l'iscrizione, aiuta Bessie a determinare quante volte vi compare come sottosequenza.
La prima riga contiene un singolo numero intero (n \le 10^5). La seconda riga contiene una stringa di caratteri, ciascuno dei quali è , oppure .
Stampa il numero di volte che compare nella stringa di input come sottosequenza, cioè le lettere non devono necessariamente essere consecutive.
Nota che la risposta può essere molto grande, quindi per i calcoli è opportuno utilizzare numeri interi a bit (ad esempio, long~long in C++ o in Java).
Esempio 1