В языке программирования 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