你听说过 Just Odd Inventions Co., Ltd. 吗？这家公司的业务是做“奇思妙想的发明”。我们姑且称它为 JOI 公司。
为了防止机密信息泄露，JOI 公司的大门安装了一道安全门。任何人进出公司都必须通过这道门，且同一时间不可能有两人或以上同时通过。
每当有人通过这道门时，系统会记录此人是进入还是离开公司。现在，JOI 公司的员工 IOI-kun 保留了某一天的门禁记录。该记录由字符串 表示：若 的第 个字符为 ‘(’，则表示第 个通过门的人是进入公司；若为 ‘)’，则表示第 个通过门的人是离开公司。IOI-kun 知道，在这一天开始和结束时，公司内均无人。请注意，存在一些仅由 ‘(’ 和 ‘)’ 组成的字符串无法表示合法记录：例如，记录不能是 ‘)(’ 或 ‘((’，因为前者意味着公司内人数曾为负数，后者意味着在当天结束时公司内仍有人员。
下一刻，IOI-kun 检查记录时，发现字符串 已被传播至 JOI 公司的计算机病毒修改！经过调查，他推测修改过程如下：
- 首先， 中的某一段连续子串被修改：对于该子串中的每个字符，若原字符为 ‘(’，则变为 ‘)’；若原字符为 ‘)’，则变为 ‘(’。我们将修改后的字符串记为 。被修改的子串长度可能为 0，即 。
- 接着， 中的 0 个或更多字符变为 ‘x’。我们将此次修改后的字符串记为 。
IOI-kun 已不记得原始字符串 ，因此他试图从 恢复 。为此，他首先希望统计所有可能成为 （注意不是 ，请小心）的字符串的数量。
任务
给定字符串 ，编写一个程序，计算所有可能成为 的字符串的数量，结果对 取模。
