Background

因为比赛水得有点过分，本团队就出了道难题。（~~出难的锅我不背~~）

Description

Jerrlee 有一个配对的括号序列（如"(())()"、 ")()"、"(()"是不符合要求的），对该序列按以下方法进行染色： 1.一个括号可以染红色、蓝色或不染色 2.一对匹配的括号需要且只能将其中一个染色 3.相邻两个括号颜色不能相同（但可以都不染色）。求符合条件的染色方案数（对1000000007取模）。

Format

Input

一行表示括号序列，且2<=序列长度<=700。

Output

一个数表示方案数（对1000000007取模）。

Sample 1

Input

()

Output

4

Sample 2

Input

(()())

Output

40

Hint

有难度的区间DP。