Once Petya read a problem about a bracket sequence. He gave it much thought but didn't find a solution. Today you will face it.

You are given string *s*. It represents a correct bracket sequence. A correct bracket sequence is the sequence of opening ("(") and closing (")") brackets, such that it is possible to obtain a correct mathematical expression from it, inserting numbers and operators between the brackets. For example, such sequences as "(())()" and "()" are correct bracket sequences and such sequences as ")()" and "(()" are not.

In a correct bracket sequence each bracket corresponds to the matching bracket (an opening bracket corresponds to the matching closing bracket and vice versa). For example, in a bracket sequence shown of the figure below, the third bracket corresponds to the matching sixth one and the fifth bracket corresponds to the fourth one.

You are allowed to color some brackets in the bracket sequence so as all three conditions are fulfilled: 
 -  Each bracket is either not colored any color, or is colored red, or is colored blue. -  For any pair of matching brackets exactly one of them is colored. In other words, for any bracket the following is true: either it or the matching bracket that corresponds to it is colored. -  No two neighboring colored brackets have the same color. 
Find the number of different ways to color the bracket sequence. The ways should meet the above-given conditions. Two ways of coloring are considered different if they differ in the color of at least one bracket. As the result can be quite large, print it modulo 1000000007 (10<sup class="upper-index">9</sup> + 7).
The first line contains the single string *s* (2 ≤ |*s*| ≤ 700) which represents a correct bracket sequence.
(())
12
(()())
40
()
4
((()))
36
()(())
42
()()()
48
(())(())
126
()()()()()()()()()()()(())
9085632
()(())()((()))
4428
()()(())()(())
5040
()()()()()()()()()()()()()()()()
411525376
(()()())
136
()(()())()
480
(())()(())()
1476
()()(()())(())()()()
195840
()()()((((())))())()()()()()((()))()()(())()(((())))()(()())((())())((()())(((((()()()())()()())))))
932124942
((()(((((()(()(())))()((((((((())))()(((((())()((((())())(()(()(())())((()))()((()))))))))))))))))))))
90824888
((()))((())())((()()))()(())(()())(())()()()((()(((()())))()())()((((()((()((())))(())(()(())())))((()())()()()((())()))()(())(())))()(((((()())))))))
100627207
()(((()((((()())))())(())(((((()(()()))))()()))((())))()())((())))(())()((()())())()(()(()())())(()())()(()(((((()))()((()()(())()(())(()((()((()))))()(())()()(()()()((((()())()))))()(((()(((((()()((((())(())))()())(()))(((())((()())(()))())(((()()()(()(())())())(()()()))))())))()((()(()()(()))())((())(()()()(())()))()()(((())))((()))(()((()(((()))((((()())))())(((())()(()((())))))))))))))))))))))
306199947
(())(((((()()()()())(())))(()()((()(()(((((())(()())))())(()()(()((())()(()()))))))(())()())))()((()()())))()()(()(())())()())()(())(((((()(()()(((()())()))((())((((()()()))())(((())(((())))))))))))))
270087235
()()()((()))(())(((())()(())(())))()()(((()((()()()))(()()(())(())))(()()((()((())(()()(()(())))))))(((())()((((()())))()(((()()())))()))()())))()(()(()())((()((()))))())(((((()())()((((()))(((((()())()))(((()()()((((((()()(())(()))((()(()(()((()((((()(((()(()()(()()((((()))()()()(()((((()(((())(((()()()(())()))((()()()(()))))())()))))(((((((()))())))(((()(()())(())))())))((((())(())())(((()()()))((()()))())(()))(())((()(()))(()()((()(()((()(())(()))()()))))))))))))))))))))))))))))))))))))))))))
461776571
()()(((((()((()(())()(()))(()(()(()(()(())(())(())(()(()((())))()))())((()((()(()(((()(()))()(()())(()()()()(((((()(((()))((((())())(((()((((()((((((())())))()))))))))(())())))(((()((()))))((())(()()))()(()(()((()())())()))))((()))))()((())())(()())()())))())())())())()((()((())((()()())()())())()(())()))(()(()))())))(()()()())()())))))))((((()())))((((()()()))())((()(())))))()((()(((())()()()(()()()()()))))(((()())()))()()(((())(()())(()()))))))
66338682
(()())()()()((((()(()()(())()((())(((()((()()(()))()))()()))))()(()(())(()))))))
639345575
()((()))((((()((())((()()((((()))()()((())((()(((((()(()))((())()))((((())()(()(()))()))))))))))))))))))
391997323
(((((()())))))()()()()()(())()()()((()()))()()()()()(((()(())))())(((()())))
422789312
((()((()))()((()(()))())))()((()())())()(()())((()))(()())(())()(())()(())(())((()()))((()))()()()()(())()
140121189
()()
14
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from functools import lru_cache
from math import factorial, comb, sqrt, gcd, lcm, log2
from copy import deepcopy
import heapq

from sys import stdin, stdout


input = stdin.readline


def main():
    MOD = 10**9 + 7
    s = input()[:-1]
    left_to_right = dict()
    right_to_left = dict()
    n = len(s)
    stack = []
    for i, c in enumerate(s):
        if c == "(":
            stack.append(i)
        else:
            cur = stack.pop()
            left_to_right[cur] = i
            right_to_left[i] = cur
    dp = [[Counter() for i in range(n)] for j in range(n)]
    # 0 代表不染色 1 代表染红色  2 代表染蓝色
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if s[i] == ")" or s[j] == "(":
                continue
            if left_to_right[i] == j:
                if j == i + 1:
                    dp[i][j][(0, 1)] = 1
                    dp[i][j][(0, 2)] = 1
                    dp[i][j][(1, 0)] = 1
                    dp[i][j][(2, 0)] = 1
                else:
                    middle = dp[i + 1][j - 1]
                    for status in [(0, 1), (0, 2), (1, 0), (2, 0)]:
                        # 外层状态
                        for key, value in middle.items():
                            if status[0] == key[0] and status[0] > 0:
                                continue
                            if status[1] == key[1] and status[1] > 0:
                                continue
                            dp[i][j][status] = (dp[i][j][status] + value) % MOD
            elif left_to_right[i] + 1 == right_to_left[j]:
                for key1, value1 in dp[i][left_to_right[i]].items():
                    for key2, value2 in dp[right_to_left[j]][j].items():
                        if key1[1] == key2[0] and key1[1] > 0:
                            continue
                        dp[i][j][(key1[0], key2[1])] = (dp[i][j][(key1[0], key2[1])] + value1 * value2) % MOD
            elif left_to_right[i] + 1 < right_to_left[j]:
                extra = dp[left_to_right[i] + 1][right_to_left[j] - 1]
                for key1, value1 in dp[i][left_to_right[i]].items():
                    for key2, value2 in extra.items():
                        if key1[1] == key2[0] and key1[1] > 0:
                            continue
                        for key3, value3 in dp[right_to_left[j]][j]:
                            if key2[1] == key3[0] and key2[0] > 0:
                                continue
                            dp[i][j][(key1[0], key3[1])] = (dp[i][j][(key1[0], key3[1])] + value1 * value2 * value3) % MOD

    print(sum(dp[0][-1].values()) % MOD)




if __name__ == "__main__":
    main()
