问题背景

给定一个仅由 '(' 和 ')' 组成的括号序列，规则括号序列 的定义如下：

• 空串是一个规则括号序列；
• 如果序列 s 是一个规则括号序列，则 (s) 也是一个规则括号序列；
• 如果序列 s 和 t 均为规则括号序列，则 st（即序列 s 和 t 的拼接）也是一个规则括号序列。

比如：序列 ()、(())()、(((())))、()(())() 均为规则括号序列；(()、)(、(()))( 均不是规则括号序列。

题目描述

本题中，给你一个字符串 $s$。$s$ 是一个规则括号序列。

我们知道，在括号序列中，每个 ( 都有它匹配的一个 )，我们称匹配的一对 ( 和 ) 为一对匹配的括号。

比如下图中：

• 蓝色的字符（第 $1$ 和 $2$ 个字符）是一对匹配的括号；
• 红色的字符（第 $3$ 和 $6$ 个字符）是一对匹配的括号；
• 绿色的字符（第 $4$ 和 $5$ 个字符）是一对匹配的括号。

现在你需要对这个规则的括号序列进行染色，染色方案需要同时遵循如下三个条件才能算是一个有效的染色方案：

1. 每一个括号要不染色，要么被染成红色，要么被染成蓝色（注：在下方的样例解释中，不染色的括号用黑色表示）。
2. 每一对匹配的括号中要求恰好有一个括号被染色，另一个括号不染色。
3. 字符串 $s$ 中任意相邻的两个括号如果都被染色的话，它们染的颜色不能一样。

求：有效的染色方案数，答案对 $10^9 + 7$ 取模。

输入格式

一行字符串 $s$。字符串 $s$ 仅由字符 ( 和 ) 构成，$2 \le |s| \le 700$ 且数据保证这是一个规则括号序列。

输出格式

输出一个整数，表示染色方案数模 $10^9 + 7$ 的结果。

样例

(())

12

(())

40

()

4

说明/提示

样例解释

下图对应的样例 1 中两种有效的染色方案：

下图对应的样例 1 中两种无效的染色方案：

（其中第一种无效是因为相邻的字符不能染同一种颜色，第二种无效是因为有一对匹配的括号都没有被染色）