题目背景
《形式语言与自动机》是 T 大学 C 系开设的一门专业基础课，在这门课程中，你能学到“常用语言类及其相应的计算模型，以及计算模型之间的联系”。这门课程涉及到不少较为晦涩难懂的理论知识；但对于你的好朋友，曾经在国际比赛中捧杯的小 A 来说，它似乎有些太简单了。
题目描述
不知道为什么，小 A 虽然上课总在做自己的事情，但是每次布置的作业他用了十几分钟就做完了。你很好奇小 A 为什么这么熟练，但眼下，小 A 上课做的事情似乎更吸引你。
“你每周上课都不认真听，是在做什么？”
“我觉得老师上课讲得还挺水的，就随便做点东西玩玩。不过充其量也就是跟课程相关的吧，随便设计点自动机什么的，测试一下它能接受什么状态。”小 A 盯着他电脑前的草稿纸说道。
过了一会，小 A 看到他屏幕上出现了一堆圆括号。你猜想他可能是设计了一个判断括号序列是否匹配的自动机。但正当你准备和小 A 搭话时，他突然指着屏幕对你说：“你说说这合理吗，我本来输了一个测试用的括号序列，结果手一滑，把光标蹭到了奇怪的地方。我就想着怎么看半天没看出来程序哪里有问题，原来是我输错了。”
你苦笑着回复说：“这不常有的事吗，反正知道问题在哪就好了。”
没想到，这句话反而让小 A 更烦躁了。
“你说常有，那我给你这个串，你试试有多少种方法把它变回一个合法的括号序列。”
诚然，你不是不会算，但是你更想听课。可惜，你没来得及打断小 A 的下一句话。
“那就这么说定了，你要是下课前没算出来，请我吃香锅。”
输入格式
输入仅包括一个串 $s$，表示小 A 实际输入的串。保证 $s$ 仅包括 ( 和 )，且二者数量相等。
输出格式
输出一个整数，表示本质不同的还原方案的个数。
我们定义一种方案可以还原一个括号序列 $s=s_1 s_2 \cdots s_n$，当且仅当存在一个划分 $s=uvw$ 使得 $uwv$ 是合法的括号序列。其中，$u=s_1\cdots s_l$ 可以为空串（此时 $l=0$），但 $v=s_{l+1}\cdots s_r$ 和 $w=s_{r+1}\cdots s_n$ 不是空串。我们称两种还原方案本质不同，当且仅当两种方案中的 $l$ 不相同或 $r$ 不相同；即使两种还原方案还原出的串相同，这两种还原方案也可能本质不同。
样例数据
样例 1 输入
()()()样例 1 输出
6样例 1 解释
所有可能的还原方案为（其中箭头前后分别为 $s=u+v+w$ 和 $uwv$）：
- $l=0,r=2$，对应 $\varepsilon$（空串，下同）$+$
()$+$()()$\Rightarrow$()()()； - $l=0,r=4$，对应 $\varepsilon+$
()()$+$()$\Rightarrow$()()()； - $l=1,r=2$，对应
($+$)$+$()()$\Rightarrow$(()())； - $l=1,r=4$，对应
($+$)()$+$()$\Rightarrow$(())()； - $l=2,r=4$，对应
()$+$()$+$()$\Rightarrow$()()()； - $l=3,r=4$，对应
()($+$)$+$()$\Rightarrow$()(())。
这些划分方案中，方案 $1,2,5$ 还原出的串和输入的串相同，但这并不影响它们划分的方式不同。
另外，()()$+$()$+\varepsilon$ 和 ()()$+\varepsilon+$() 都不是合法的还原方案，因为在前一种划分中 $w=\varepsilon$，而在后一种划分中 $v=\varepsilon$。
样例 2
见附加文件中的 2.in 与 2.ans。
样例 3
见附加文件中的 3.in 与 3.ans。
子任务
对于 $100\%$ 的数据，保证 $1\le |s| \le 10,000,000$。
提示
你不需要掌握《形式语言与自动机》这门课程的相关知识也能通过本题。
另外，《形式语言与自动机》这门课程“很简单”的说法只是本题中虚构人物小 A 的看法，不代表出题人的意见。