括号匹配问题想必大家都再熟悉不过了，龙龙在此基础上，想出了一个升级版的问题，但是他不知道如何解决，所以这个重任就交给了你们。

问题是这样的，给你一个括号序列s（长度不超过700），s序列满足：① s序列只包含”(“和”)”两种字符；② s序列能够通过插入运算符和数字构成正确的数学表达式（即每个“（“都有“）”与之匹配，且“（“总在与之匹配的”）“出现之前出现）。例如“（（（）（）））“、”（）（）（）“等都是满足要求的s序列；”（））（）“、”（））（（）“是不满足要求的，他们不是s序列。现在龙龙想为s序列的每个“(“或者”)”染色。染色遵循如下三个标准：

①     每个括号要么不染色、要么染蓝色、要么染红色。

②     任何一对匹配的括号对有且只有一个染成蓝色或红色。

③     相邻的两个括号不能被染成相同的颜色（但可以都不染色）。

龙龙的问题是求出所有不同的染色方案。如果两个被染色后的s序列至少有一个位置颜色不同，则认为这两种染色方案是不同的。