题目背景

给括号序列每个半括号染色。 要求：

• 1.不染色或者染红/蓝色；
• 2.一对括号正好有一半染色；
• 3.相邻括号不能染相同颜色。

方案数？

题目描述

给你一个字符串 $s$ 。它代表一个合法的括号序列。

你需要为括号序列中的某些括号染色，以满足所有三个条件：

• 每个括号要么不染色，要么染红色，要么染蓝色。
• 没有两个相邻的染色括号具有相同的颜色。
• 对于任何一对匹配的括号，其中正好有一个染色。

计算给括号序列染色的方案数。输出答案对 $10^9+7$ 取模的结果。

输入格式

第一行输入一个字符串 $s ( 2 ≤ |s| ≤ 700 )$，代表一个合法的括号序列。

输出格式

输出给括号序列染色的方案数对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

(())

输出 #1

12

输入输出样例 #2

输入 #2

(()())

输出 #2

40

输入输出样例 #3

输入 #3

()

输出 #3

4

说明/提示

对于$30\%$ 的数据：$1\le |s|\le 20$

对于$60\%$ 的数据：$1\le |s|\le 40$

对于$100\%$ 的数据：$1\le |s|\le 700$