题目背景

一个合法的括号序列定义如下：

• 空串是合法序列。
• 如果 A 是合法序列，则 (A),[A] 都是合法序列。
• 如果 A,B 是合法序列，则 AB 是合法序列。

题面描述

给定一个长度为 $N$ 的只包含小括号的括号序列，你可以将一些 $\texttt{(}$ 替换成 $\texttt{[}$ 或 $\texttt{]}$，也可以不替换。你需要求出能得到多少合法的括号序列。

答案可能很大，输出对 $10^9 + 7$ 取模后的结果。

输入格式

第一行一个正整数 $n$ 表示串的长度。

第二行一个长度为 $n$ 的只包含 $\texttt{(,)}$ 的串。

输出格式

输出一个整数表示答案。注意答案对 $10^9+7$ 取模。

Samples

8
((((((((

14

12
(((()())((()

11

4
((((

2

样例3解释

两个合法方案分别是 [[]] 和 [][]。

数据范围与约定

对于 $100\%$ 的数据，保证 $2\le N\le 15000$。

本题共 $10$ 个测试点。

对于测试点 $1$，$N\le 16$。

对于测试点 $2$，$N\le 100$。

对于测试点 $3,4$，$N\le 600$。

对于测试点 $5,6$，$N\le 2000$。

对于测试点 $7$，保证串只包含 $\texttt{(}$。