CF909C.Python Indentation

In Python, code blocks don't have explicit begin/end or curly braces to mark beginning and end of the block. Instead, code blocks are defined by indentation.

We will consider an extremely simplified subset of Python with only two types of statements.

Simple statements are written in a single line, one per line. An example of a simple statement is assignment.

For statements are compound statements: they contain one or several other statements. For statement consists of a header written in a separate line which starts with "for" prefix, and loop body. Loop body is a block of statements indented one level further than the header of the loop. Loop body can contain both types of statements. Loop body can't be empty.

You are given a sequence of statements without indentation. Find the number of ways in which the statements can be indented to form a valid Python program.

在 Python 中，代码块没有显式的起始/结束标记或花括号来标识其起始与结束；相反，代码块由缩进定义。

我们将考虑一个极度简化的 Python 子集，其中仅包含两种类型的语句：

• 简单语句：每行仅写一条，占据单独一行。例如赋值语句即为一种简单语句。
• for 语句：属于复合语句，其内部包含一个或多个其他语句。for 语句由一行“头”（header）开始，该行以 for 前缀开头；其后是循环体（loop body）。循环体是一组语句块，其缩进比 for 头多一个层级。循环体中可包含上述两类语句中的任意一种。循环体不能为空。

现给你一段未缩进的语句序列，请计算有多少种方式为其添加缩进，使其构成一个合法的 Python 程序。

The first line contains a single integer N (1 ≤ N ≤ 5000) — the number of commands in the program. N lines of the program follow, each line describing a single command. Each command is either "f" (denoting "for statement") or "s" ("simple statement"). It is guaranteed that the last line is a simple statement.

第一行包含一个整数 $N$（$1 \leq N \leq 5000$），表示程序中命令的数量。接下来有 $N$ 行，每行描述一条命令。每条命令要么是 "f"（表示“for 语句”），要么是 "s"（表示“简单语句”）。保证最后一行为简单语句。

Output one line containing an integer - the number of ways the given sequence of statements can be indented modulo 109 + 7.

输出一行，包含一个整数——给定语句序列的缩进方式数目对 $10^9 + 7$ 取模的结果。

In the first test case, there is only one way to indent the program: the second for statement must be part of the body of the first one.

simple statement
for statement
for statement
simple statement

In the second test case, there are two ways to indent the program: the second for statement can either be part of the first one's body or a separate statement following the first one.

for statement
simple statement
for statement
simple statement

or

for statement
simple statement
for statement
simple statement

在第一个测试用例中，只有一种缩进程序的方式：第二个 for 语句必须是第一个 for 语句体的一部分。

简单语句
for 语句
for 语句
简单语句

在第二个测试用例中，有两种缩进程序的方式：第二个 for 语句既可以作为第一个 for 语句体的一部分，也可以作为跟在第一个 for 语句之后的独立语句。

for 语句
简单语句
for 语句
简单语句

或

for 语句
简单语句
for 语句
简单语句