Корова#11177
Корова Бессі натрапила на загадковий напис, викарбуваний на великому камені посеред її улюбленого пасовища. Схоже, що напис зроблено давньою таємничою мовою, алфавіт якої складається лише з трьох символів: , та . Хоча Бессі не може розшифрувати цей текст, вона помітила, що , та , записані послідовно, утворюють її улюблене слово. Тепер їй цікаво, скільки разів слово зустрічається в цьому написі.
Бессі не заперечує, якщо між буквами трапляються інші символи — важливо лише, щоб букви , та розташовувалися у правильному порядку. Крім того, різні входження можуть використовувати одні й ті самі букви. Наприклад, зустрічається один раз у рядку , двічі у та вісім разів у CCOOWW.
За даним текстом напису допоможіть Бессі визначити, скільки разів зустрічається в ньому як підпослідовність.
У першому рядку міститься одне ціле число (n \le 10^5). У другому рядку міститься рядок з символів, кожен з яких є , або .
Виведіть кількість разів, яку зустрічається у вхідному рядку як підпослідовність, тобто букви не обов'язково повинні розташовуватися поспіль.
Зверніть увагу, що відповідь може бути дуже великою, тому для обчислень слід використовувати -бітні цілі числа (наприклад, long~long у C++ або у Java).
Приклад 1