CF149D Coloring Brackets
题目描述
### 题意描述
给出一个配对的括号序列（如 “$\texttt{(())()}$”、“$\texttt{()}$” 等，“$\texttt{)()}$”、“$\texttt{(()}$”是不符合要求的），对该序列按照以下方法染色。
1. 一个括号可以染成红色、蓝色或者不染色。
2. 一对匹配的括号需要且只能将其中一个染色。
3. 相邻两个括号颜色不能相同（但都可以不染色）。
求符合条件的染色方案数，对 $1000000007$ 取模。
输入格式
无
输出格式
无
说明/提示
Let's consider the first sample test. The bracket sequence from the sample can be colored, for example, as is shown on two figures below.
The two ways of coloring shown below are incorrect.
