题目描述

有一次，Petya 读到一道关于括号序列的题目。他苦思冥想也没找到解法。今天这道题摆在了你的面前。

给定字符串 $s$，它是一个合法括号序列。合法括号序列是由左括号 "(" 和右括号 ")" 组成、能够在括号之间插入数字和运算符后得到正确数学表达式的序列。例如 "(())()" 和 "()" 是合法括号序列，而 ")()" 和 "(()" 不是。

在合法括号序列中，每个括号都与唯一一个配对括号对应（左括号对应配对的右括号，反之亦然）。例如下图所示的括号序列中，第 3 个括号与第 6 个括号配对，第 5 个括号与第 4 个括号配对。

你可以给括号序列中的一些括号染色，要求同时满足以下三个条件：

• 每个括号要么不染色，要么染红色，要么染蓝色；
• 对任何一对配对括号，恰好其中一个被染色。换句话说，对任何括号，要么它自己被染色，要么与它配对的那个括号被染色；
• 相邻两个被染色的括号颜色不能相同。

求满足上述条件的染色方案数。只要至少一个括号的颜色不同，两个方案就算不同。由于结果可能很大，输出对 $10^9+7$ 取模的结果。

输入格式

第一行包含字符串 $s$（$2 \le |s| \le 700$），保证是一个合法括号序列。

输出格式

输出一个数——满足上述条件的染色方案数对 $10^9+7$ 取模的结果。

(())

12

(()())

40

()

4

说明/提示

看第一组样例：样例中的括号序列可以像下面两幅图那样染色。

而下面两种染色方式是不合法的。