← 返回题目列表

Codeforces · 909/C

C. Python 缩进

中文机器翻译题面 查看原题

在 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