D. 着色括号

每次测试时间限制：$2$ 秒
每次测试内存限制：$256$ 兆字节

有一次，佩佳读到一道关于括号序列的问题。他想了很久，但没找到解决办法。今天你将面对它。

你被给定一个字符串 $s$，它代表一个正确的括号序列。正确的括号序列是由开括号 ( 和闭括号 ) 组成的序列，使得可以在括号之间插入数字和运算符后得到一个正确的数学表达式。例如，(() )() 和 () 是正确的括号序列，而 )( 和 (() 则不是。

在正确的括号序列中，每个括号都有一个匹配的括号（开括号匹配对应的闭括号，反之亦然）。

你可以给括号序列中的部分括号涂色，需满足以下三个条件：

1. 每个括号要么不涂色，要么涂成红色，要么涂成蓝色。
2. 对于任意一对匹配的括号，恰好有一个被着色。
   —— 即对于任意括号，要么它自己，要么它的匹配括号，被着色。
3. 没有两个相邻的彩色括号颜色相同。

请找出所有满足上述条件的括号序列着色方式的数量。如果至少有一个括号的颜色不同，则两种着色方式视为不同。由于答案可能很大，请输出它对 $10^9+7$ 取模的结果。

输入

第一行包含一个字符串 $s$（$2 \le |s| \le 700$），代表一个正确的括号序列。

输出

输出唯一的数字 —— 满足上述条件的括号序列着色方式的数量，对 $10^9+7$ 取模。

示例

输入

(())

输出

12

输入

(()())

输出

40

输入

()

输出

4

注释

在第一个样例中，括号序列可以被涂色，如下图所示。

下面显示的两种着色方式是错误的。