小红的括号串
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

\,\,\,\,\,\,\,\,\,\,小红有一个只包含 '(' 、')' 和 '?' 的字符串，小红想知道有多少种将 '?' 替换成 '(' 或 ')' 的方式使得存在一种循环移位、让该字符串为合法的括号串。
\,\,\,\,\,\,\,\,\,\,假设一个长度为 n 的字符串 s[k:n] + s[1:k) 是字符串 s 的循环移位，且 s[k:n] + s[1:k) 是一个合法的括号串，那么字符串 s 符合题目要求。

输入描述:

\,\,\,\,\,\,\,\,\,\,第一行输入一个整数 n\ (1 \le n \le 10^5) 代表字符串长度。
\,\,\,\,\,\,\,\,\,\,第二行输入一个长度为 n ，且只由 '(' 、')' 和 '?' 三种字符组成的字符串 s 。

输出描述:

\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，代表合法替换方式数量。由于答案可能很大，你需要输出答案对 10^9 + 7 取模的结果。
示例1

输入

复制 
10
()(??(?)??

输出

复制 
10

说明

其中一种替换方式为：()())())((，可以循环移位得到 ((()())())，是合法的括号串。