CF149D Coloring Brackets
题目描述
### 题意描述
给出一个配对的括号序列（如 “$\texttt{(())()}$”、“$\texttt{()}$” 等，“$\texttt{)()}$”、“$\texttt{(()}$”是不符合要求的），对该序列按照以下方法染色。
1. 一个括号可以染成红色、蓝色或者不染色。
2. 一对匹配的括号需要且只能将其中一个染色。
3. 相邻两个括号颜色不能相同（但都可以不染色）。
求符合条件的染色方案数，对 $1000000007$ 取模。
输入格式
一行一个字符串 $s$，表示括号序列（$2 \leqslant |s| \leqslant 700$）。
输出格式
一个数字，表示染色的方案数（对 $1000000007$ 取模）。
说明/提示
样例一可以如下图所示着色（其中两种）：
下面的两种着色方式是不正确的：
