生成括号序列

题目描述

刚学完用栈进行括号匹配的程序设计竞赛新手 Mandy 突发奇想，想到了一种括号序列的生成方式（只考虑小括号）：一开始从 $()$ 开始生成，设当前括号序列为 $S$，可以进行两种操作：

1. 在序列最右边添加一对括号，即 $S \rightarrow S()$
2. 选取一个 S 的区间 $[l, r]$， 要求这个区间内的括号是一个合法的括号序列，然后在这个区间外增加一对括号将其括在其中。例如 $(()())\rightarrow((())())$（选取区间 [2, 3]）

Mandy 用这个生成方式生成了一个括号序列 $A$，但是她马上发现，还有很多种不同的生成方式也能得到 $A$，于是她陷入了困惑之中：究竟有多少种不同的生成方式呢？（操作二选取不同的区间视为不同的操作） 喜欢计数的 brz 使用枚举大法很快就得出了答案，但是当 $A$ 变得更长时，他的做法就不太有效了。 现在他想要找你帮忙解决 Mandy 的困惑，你能快速地求出这个问题的答案吗？

输入格式

输入一行，包含一个由 "("和 ")"构成的字符串 $A (1 ≤ |A| ≤ 10^6)$。保证 $A$ 是个合法的括号序列。

输出格式

输出一行，表示不同的操作顺序数。由于答案可能很大，所以你只需要输出答案对 $998 244 353$ 取 模后的结果即可。

样例 #1

样例输入 #1

(())()

样例输出 #1

2