在 Python 中,代码块没有显式的开始/结束或大括号来标记块的开始和结束。相反,代码块是通过缩进定义的。
我们将考虑一个极其简化的 Python 子集,只有两种类型的语句。
简单的语句写在一行中,每行一个。简单语句的一个例子是赋值。
For 语句是复合语句:它们包含一个或多个其他语句。 For 语句由写在单独行中的标题和循环体组成,该标题以“for”前缀开头。循环体是比循环头缩进一级的语句块。循环体可以包含两种类型的语句。循环体不能为空。
您将获得一系列不带缩进的语句。找出语句可以缩进以形成有效的 Python 程序的方式数。
输入
第一行包含一个整数 N (1 ≤ N ≤ 5000) — 程序中的命令数。接下来是 N 行程序,每行描述一个命令。每个命令要么是“f”(表示“for 语句”),要么是“s”(“简单语句”)。保证最后一行是一个简单的语句。
输出
输出一行,其中包含一个整数 - 给定语句序列可以缩进模 109 + 7 的方式数。
示例
输入 #1
4 s f f s
输出 #1
1
输入 #2
4 f s f s
输出 #2
2
注意
在第一个测试用例中,只有一种方法可以缩进程序:第二个 for 语句必须是第一个 for 语句主体的一部分。
在第二个测试用例中,有两种方法来缩进程序:第二个 for 语句可以是第一个语句主体的一部分,也可以是第一个语句后面的单独语句。
or