D. Магазин шляп
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На витрине магазина выложено n шляп, пронумерованных слева направо от 1 до n. Шляпы бывают трёх видов: мужские, женские и универсальные. В магазин по очереди заходят покупатели, причём каждый следующий покупатель может оказаться как мужчиной, так и женщиной.

Каждый покупатель идет вдоль витрины слева направо и выбирает первую подходящую ему шляпу. Так, покупатель-мужчина выберет самую левую среди мужских и универсальных шляп, а покупатель-женщина выберет самую левую среди женских и универсальных шляп. Если ни одной подходящей шляпы на витрине нет, покупатель уходит без покупки. Каждый раз, когда кто-то покупает одну из шляп, продавец записывает номер купленной шляпы.

К концу дня все шляпы были раскуплены, и у продавца оказалась записана перестановка чисел от 1 до n. Сколько существует возможных вариантов этой перестановки? Так как ответ может быть довольно большим, определите остаток от его деления на 109 + 7.

Входные данные

В первой строке записано одно целое число n (1 ≤ n ≤ 5000) — количество шляп на витрине.

Во второй строке записано n символов — типы шляп в порядке нумерации. Символ «M» означает мужскую шляпу, символ «W» — женскую шляпу, а символ «U» — универсальную шляпу.

Выходные данные

Выведите остаток от деления ответа на 109 + 7.

Примеры
Входные данные
3
UMW
Выходные данные
2
Входные данные
3
MWU
Выходные данные
4
Примечание

В первом примере первый покупатель обязательно купит первую шляпу (независимо от пола). Оставшиеся две шляпы могут быть куплены в любом порядке.

Во втором примере возможны следующие перестановки: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1).