筱玛的字符串
题号：NC21814
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

筱玛是一个快乐的男孩子。
筱玛有一个合法的括号匹配串S，但是被!b!b和ipip给偷走了！
!b!b把S中连续一段的字符给反转（即左括号变成右括号，右括号变成左括号），称为S'。
注意!b!b可能并没有反转。
ipip把S'其中的一些字符变成了?，称为S''。
筱玛很生气，但是他只知道S''。
请你求出所有可能的(S,S')对的个数，对取模。

输入描述:

一行一个字符串S。

输出描述:

一行一个整数，表示模意义下的答案。
示例1

输入

复制 
??))

输出

复制 
7

说明

()(),()))
()(),(())
()(),)())
(()),(())
(()),()))
(()),)())
(()),))))

备注:


保证输入字符只包含'(',')'和'?'。