C. Отступы в Python
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В языке программирования Python блоки кода не выделяются ключевыми словами begin/end или фигурными скобками. Вместо этого используются отступы.

Мы рассмотрим очень упрощенный вариант Python, с двумя типами инструкций.

Простые инструкции записываются в одной строке, по одной инструкции на строку. Примером такой инструкции является присваивание.

Циклы являются составными инструкциями: они содержат одну или несколько других инструкций. Цикл состоит из заголовка, записанного в отдельной строке и начинающегося с префикса "for", и тела цикла. Тело цикла — блок инструкций, записанных с отступом на один уровень дальше, чем заголовок цикла. Тело цикла может содержать оба типа инструкций, и не может быть пустым.

Вам дана последовательность инструкций, записанных без отступов. Найдите количество способов, которыми можно расставить отступы так, чтобы получить валидную программу.

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

Первая строка входных данных содержит одно число N (1 ≤ N ≤ 5000) — количество инструкций в программе. Следующие N строк описывают программу, по одной инструкции на строку. Каждая строка состоит из одного символа: "f" (цикл) или "s" (простая инструкция). Гарантируется, что последняя строка программы — "s".

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

Выведите одно число — количество способов, которыми можно расставить отступы в заданной последовательности инструкций, чтобы получить валидную программу, по модулю 109 + 7.

Примеры
Входные данные
4
s
f
f
s
Выходные данные
1
Входные данные
4
f
s
f
s
Выходные данные
2
Примечание

В первом примере есть ровно один способ расставить отступы: второй цикл должен быть частью тела первого цикла.


simple statement
for statement
    for statement
        simple statement

Во втором примере расставить отступы можно двумя способами: второй цикл может быть либо частью тела первого, либо следующей за ним инструкцией.


for statement
    simple statement
    for statement
        simple statement

или


for statement
    simple statement
for statement
    simple statement