对于字符串 S 与 T，如果从 S 中删除任意多个字符可以得到 T，那么 T 是 S 的子序列。换言之，T 是选取 S 中的若干字符按下标顺序连接而成的。两个子序列不同当且仅当所选取的下标不同。

例如 sun 是 sequence 的子序列，因为从 sequence 中删除 eq、e 和 ce 可以得到 sun；sequence 有 2^8 个不同的子序列，其中有空字符串，也有三个不同的子序列 e，因为 sequence 的第 2,5,8 个字符都为 e，分别保留这三个字符得到的子序列是不同的。

对于字符串 S，如果 S 满足以下条件那么 S 是合法括号序列：

• S 是空字符串，或者
• S 可由 (、合法括号序列、) 三者连接得到，或者
• S 可由两个合法括号序列连接得到。

例如 ()、()()、(()) 和 (()()) 都是合法括号序列。但是 (()、)( 不是合法括号序列。

给定一个长度为 n 的仅包含 ( 与 ) 的字符串 S。请你求出 S 所有 2^n 个子序列中有多少个合法括号序列。由于答案可能很大，请你输出答案对 10^9 取模的结果。

例如，S 为 ))(()( 时共有 3 个子序列是合法括号序列，分别为空字符串与两个不同的子序列 ()。

第一行，一个正整数 n，表示字符串 S 的长度。

第二行，长度为 n 的仅包含 ( 与 ) 的字符串 S。

输出一行，一个整数，表示 S 的合法括号子序列的数量对 10^9 取模的结果。

数据范围

对于 40\% 的测试点，保证 1\le n\le400。

对于所有测试点，保证 1\le n\le2000。

GESP七级26年9月