J18 习题-3 括号涂色

题目描述

给定一个只包含 ‘(’ 和 ‘)’ 的字符串，保证其为一个合法的括号序列，对每个（左）右括号分别染色，要求满足：

1、每个括号不涂颜色，或者染成红色，或者染成蓝色。

2、每一对匹配的括号恰好有一个被染色。

3、没有两个相邻的带色括号具有相同的颜色。

求为括号序列上色的不同方案数。如果两种着色方式的至少一个括号的颜色不同，则认为它们是不同的。结果可能会很大，

模 $1000000007$（$1e9 + 7$）输出。

输入格式

第一行包含单个字符串 $s$，表示一个合法的括号序列。

输出格式

一个整数，表示染色方案数（模 $1e9+7$ )。

样例输入1

(())

样例输出1

12

样例输入2

(()())

样例输出2

40

样例输入3

()

样例输出3

4

样例分析

如上所述。

数据范围

$100\%$ 的数据：$0 < |s| \leq 700$。