抄代码

题目描述

你眼前出现了三个屏幕，第一个屏幕上有一个奇怪程序。

这个程序有很多行，是用小明写成的。

小明的语法如下：

1. 一个普通语句占一行；
2. 一对大括号分别占一行，表示一层嵌套的程序；
3. 同一层程序中的普通语句顺序可以互换；
4. 对于每一层程序，在两个大括号之间有若干行，先写完所有普通语句，才可以写嵌套的程序，且每层程序最多只会嵌套一个程序（层与层间的包含关系不可改变）；

例如以下情况不合法：

• 一层程序嵌套了多个程序

{
a = 1;
{
b = 1;
}
{
c = 1;
}
}

• 普通语句未写完就写嵌套了

{
a = 1;
{
b = 1;
}
c = 1;
}

抄写时，可以把一块屏幕的最下面一条语句抄到另一块屏幕的最下面，并且将这条语句从原来的地方擦掉。大括号可以任意擦除或写入。

现在需要从第一个屏幕将程序抄到第三个屏幕上。

输入格式

输入有若干行字符，表示这个程序，保证给出的程序合法。

输出格式

输出一行一个整数表示答案对$10^{9}+7$取模的结果。

注意大括号的抄写不算入答案且抄写过程中也必须保证程序合法。

数据范围与提示

保证：

1. 每行长度不超过$20$；
2. 每层程序至少有一句普通语句；
3. 除了最内层程序，每层程序均恰有一个嵌套程序；
4. 所有大括号严格对应，且文件以"{"开始，以"}"结束；
5. 大括号前后不会有空格；
6. 你不必管语句内容，同一层的普通语句一定可以互换。

对于$10\%$的数据，行数小于$20$且嵌套层数不超过$3$； 对于$30\%$的数据，行数小于$1000$且嵌套层数不超过$20$； 对于$100\%$的数据，行数小于$100000$且嵌套层数不超过$1000$。

样例

{
a = 0;
b = 1;
{
c = a + b;
}
}

4

说明

第零步，无视所有的大括号（反正可以抄完了再加）。

第一步，把c=a+b;抄到第二块屏幕上。

第二步，把b=1;抄到第三块屏幕上。

第三步，把a=0;抄到第三块屏幕上。

第四步，把c=a+b;抄到第三块屏幕上。

最终步，补上大括号。

由于大括号的擦除和写入不算入抄写次数，因此是$4$步。