U360425 括号序列

给你一个长度为 $n$ 的字符串。 由 $( ) *$ 三种符号组成。 其中 $*$ 表示未知符号，可能是 $"("$ 或者 $")"$ 且概率相等。 我们设字符串 $A$ 是合法的，且它的权值是 $v$ 当且仅当存在权值为 $w$ 的字符串 $B$ ，满足 $$ A=(B),v=w+1 $$ $$ A=B(),v=w $$ $$ A=(),v=1 $$ 其中任意一种。 求 $A$ 的子序列中最大权值的期望值。 子序列的定义是一个下标的子集的合并。 例如序列 [2,5,6,7] 就有子序列 [5,7]。

第一行一个正整数 $n$ 。 长度为$n$ 的字符串 $s$ ，$s$ 中仅有 $()*$ 三种字符。

一行一个整数，答案对 $10^9+7$ 取模。

样例1解释，一共有8种， $20\%$ 的数据， $n\le 20$。 $60\%$ 的数据， $n\le 2000$ 。 $100\%$ 的数据， $20\le n\le 10^6$。 字符串只有 $()*$ 三种字符、