对于字符串 ，，定义 的字典序小于 当且仅当以下三者之一成立：
- 为空串（长度为 ）， 为非空串；
- 为非空串，且 字典序小于 ，这里 表示 的首个字符；
- 为非空串，且 ， 字典序小于 ，这里 表示 删除首个字符得到的字符串。
对于由 组成的括号串 ，称其为可匹配的，当且仅当以下三者之一成立：
- 是空串（长度为 ）；
- ，其中 是可匹配的括号串；
- ，其中 ， 都是可匹配的非空括号串。
下面给出一个可匹配的括号串 ，求有多少个括号串 满足以下四个条件：
- 不是空串（长度大于 ）；
- 是可匹配的；
- ，或 的字典序小于 ；
- 的长度小于等于 的长度。
注意，符号 小。
本题采用多组测试。答案可能很大，请输出结果对 取模后的余数。
