有一次,Petya 读到了一个关于括号序列的问题。他想了很多,但没有找到解决办法。今天你将面对它。
给定了字符串 s。它代表正确的括号序列。正确的括号序列是左括号(“(”)和右括号(“)”)的序列,这样可以通过在括号之间插入数字和运算符来从中获得正确的数学表达式。例如,“(())()”和“()”等序列是正确的括号序列,而“)()”和“(()”等序列则不是。
在正确的括号序列中,每个括号对应于匹配的括号(左括号对应于匹配的右括号,反之亦然)。例如,在下图所示的括号序列中,第三个括号对应匹配的第六个括号,第五个括号对应第四个括号。
您可以为括号序列中的某些括号着色,以便满足所有三个条件:
- 每个括号要么没有任何颜色,要么是红色,要么是蓝色。
- 对于任何一对匹配的括号,其中一个是彩色的。换句话说,对于任何括号,以下情况都是正确的:它或与其对应的匹配括号是彩色的。
- 两个相邻的彩色括号没有相同的颜色。
找出为括号序列着色的不同方法的数量。该方法应满足上述条件。如果两种着色方式至少有一个括号的颜色不同,则认为它们不同。由于结果可能相当大,因此打印它对 1000000007 (109 + 7) 取模。
输入
第一行包含单个字符串 s (2 ≤ |s| ≤ 700),它表示正确的括号序列。
输出
打印唯一的数字 — 满足上述给定条件的括号序列着色方式的数量模 1000000007 (109 + 7)。
示例
输入 #1
(())
输出 #1
12
输入 #2
(()())
输出 #2
40
输入 #3
()
输出 #3
4
注意
让我们考虑第一个示例测试。示例中的括号序列可以着色,例如,如下两图所示。
下面所示的两种着色方式是不正确的。