三色括号序列

你有一个长度为$n$的序列，其中每个位置必定是(,)之一，此外，每个括号是有红绿蓝三种颜色之一的。也就是说，这个序列每个位置有“红色(,)，绿色(,)，蓝色(,)六种可能，这个序列共有$6^n$种可能。

一个序列是合法的，当且仅当满足：

（1）仅保留红绿两种颜色的括号，这个括号序列是合法的。

（2）仅保留红蓝两种颜色的括号，这个括号序列是合法的。

（3）仅保留蓝绿两种颜色的括号，这个括号序列是合法的。

对于输入的$n$，请输出有多少种合法的括号序列。

输入格式

第一行输入一个数字$n$。

第二行输入一个长度为$n$的字符串$S$，其中$S_i=$?,(,)之一。

(,)代表这个位置是左括号还是右括号已经被指定，?代表这个位置可以是任何一种括号。

输出格式

输出答案$\mod 998244353$。

样例输入1

6
()()()

样例输出1

27

样例输入2

6
??????

样例输出2

297

数据范围

$n\leq 300$，保证$n$是偶数。

经优化后std只需要$1s$，所以$2s$时限很合理。