题目描述

给定一个只包含 ( 和 ) 的字符串 $s$，保证 $s$ 是一个合法括号序列。请给每个括号染色，要求满足以下条件：

1. 每个括号可以不染色，或者染成红色，或者染成蓝色；
2. 每一对匹配的括号恰好有一个括号被染色；
3. 任意两个相邻的有色括号颜色不能相同。

如果两种着色方式至少有一个括号的颜色不同，则认为它们不同。请计算不同染色方案数，并对 $1000000007$ 取模。

输入格式

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

输出格式

输出一行一个整数，表示染色方案数对 $1000000007$ 取模后的结果。

(())

12

(()())

40

()

4

数据范围与提示

• $1 \le |s| \le 700$