题目背景

《形式语言与自动机》是 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$ 不相同；即使两种还原方案还原出的串相同，这两种还原方案也可能本质不同。

()()()

6

提示

【样例解释】

所有可能的还原方案为（其中箭头前后分别为 $s=u+v+w$ 和 $uwv$）：

1. $l=0,r=2$，对应 $\varepsilon$（空串，下同）$+$()$+$()() $\Rightarrow$ ()()()；
2. $l=0,r=4$，对应 $\varepsilon+$()()$+$()$\Rightarrow$()()()；
3. $l=1,r=2$，对应 ($+$)$+$()()$\Rightarrow$(()())；
4. $l=1,r=4$，对应 ($+$)()$+$()$\Rightarrow$(())()；
5. $l=2,r=4$，对应 ()$+$()$+$()$\Rightarrow$()()()；
6. $l=3,r=4$，对应 ()($+$)$+$()$\Rightarrow$()(())。

这些划分方案中，方案 $1,2,5$ 还原出的串和输入的串相同，但这并不影响它们划分的方式不同。

另外，()()$+$()$+\varepsilon$ 和 ()()$+\varepsilon+$() 都不是合法的还原方案，因为在前一种划分中 $w=\varepsilon$，而在后一种划分中 $v=\varepsilon$。

【数据范围】

对于 $100\%$ 的数据，保证 $1\le |s| \le 10,000,000$。

【提示】

你不需要掌握《形式语言与自动机》这门课程的相关知识也能通过本题。

另外，《形式语言与自动机》这门课程“很简单”的说法只是本题中虚构人物小 A 的看法，不代表出题人的意见。

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）。

题解等资源可在 https://github.com/yylidiw/thupc_0/tree/master 查看。