CF909C Python Indentation

在 Python 中，代码块没有明确的 begin/end 或大括号来标记开始和结束。相反，代码块是通过缩进来定义的。 我们将考虑一个极其简化的 Python 子集，其中只有两种类型的语句。 **简单语句**用单行书写，每行一条。赋值就是简单语句的一个例子。 **for 语句**是复合语句：它们包含一个或多个其他语句。For 语句由以“for”前缀开头的单行标题和循环体组成。循环体是比标题缩进一级的语句块。循环体可以包含两种类型的语句。特别地，循环体不能为空。 现在给你一串没有缩进的语句。请找出有多少种缩进方式可以使这些语句组成一个有效的 Python 程序。

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

输出给定语句序列的缩进方案数，对 $10^9 + 7$ 取模。

#### 样例解释 #1 在第一个测试用例中，只有一种缩进程序的方法：第二个 for 语句必须是第一个 for 语句循环体的一部分。 ``` 简单语句 for 语句 for 语句 简单语句 ``` #### 样例解释 #2 在第二个测试用例中，有两种缩进程序的方法：第二个 for 语句既可以是第一个 for 语句循环体的一部分，也可以是第一个 for 语句之后的一个单独语句。 ``` for 语句 简单语句 for 语句 简单语句 ``` 或 ``` for 语句 简单语句 for 语句 简单语句 ```