缩进问题(Indentation Problem)

题目描述

Python 语言通过缩进的深度来表达语句所属的块。例如有如下代码：

for i in range(0, 10):
 for j in range(0, 100):
 a = a + 1
 b = b + 2

因为 a = a + 1 缩进最深，所以它属于内层循环，而 b = b + 2 缩进较浅，所以它属于外层循环。

Python 的另一个特点是，每条循环语句的循环体不能空，至少需要包含一条语句。

不幸的是，目前有一段 Python 代码的缩进全部消失了，请你计算一下，这段信息不全的代码，可能有多少种不同嵌套结构？

输入格式

第一行：单个整数 $n$，表示代码的行数；

接下来 $n$ 行：每行一个字符：

• 字符 f 表示这是一行以 for 开头的循环语句；
• 字符 = 表示这是一行赋值语句，为了保证程序至少有一种合理的解释，保证最后一个字符一定是 =。

输出格式

单个整数：表示输入代码的不同逻辑结构数量，由于可能比较大，输出模 $10^9+7$ 的余数。

样例输入 #1

4
=
f
f
=

样例输出 #1

1

样例输入 #2

4
f
=
f
=

样例输出 #2

2

数据范围

• 对于 30% 的数据，$1\leq n\leq 20$；
• 对于 60% 的数据，$1\leq n\leq 500$；
• 对于 100% 的数据，$1\leq n\leq 7000$。

知识点与难度

本题涉及的知识点从属于 GESP 6级（动态规划、前缀和优化），难度等级：⭐⭐⭐。

测试点分布