题目描述

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 代码的缩进全部消失了，请你计算一下，这段信息不全的代码，可能有多少种不同嵌套结构？例如

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

除了上一种结构外，还有一种结构为

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

输入格式

第一行：单个整数 $n$，表示代码的行数； 接下来 $n$ 行：每行一个字符：

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

输出格式

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

4
=
f
f
=

1

样例解释 1

只有唯一的一种解释

4
f
=
f
=

2

数据范围

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