题目描述

爱丽丝有一个有效的括号序列 $s^*$，她想通过一个嘈杂的通道与鲍勃分享它。对于每个字符，该通道以 $1/2$ 的概率独立地将该字符传输给鲍勃，或者以 $1/2$ 的概率将一个无法区分的字符 ? 传输给鲍勃。例如，如果爱丽丝的有效括号序列是 $s =$ (()()) ，鲍勃可能收到字符序列 (?)())、?(??)?，但不能收到字符序列 ??(())。在收到消息后，鲍勃尝试重建爱丽丝传输的有效括号序列。然而，爱丽丝知道在某些情况下，重建不是唯一的；例如，当收到字符序列 ?(??)? 时，有两个可能的重建：(()()) 和 ((()))。请帮助爱丽丝计算鲍勃收到的消息能够唯一重建有效括号序列的概率。输出答案模 $998244353$。

• 括号序列 $s$ 是有效的，如果以下任一条件成立：

1. $s$ 是空的；
2. $s = `(` + t + `)`$ ，其中 $t$ 是一个有效的括号序列；
3. $s = t_1 + t_2$，其中 $t_1$ 和 $t_2$ 是有效的括号序列。

输入格式

输入由一行组成，包含一个有效的括号序列 $s\ (2 \leq |s| \leq 10^6)$。

输出格式

输出一个整数，表示鲍勃收到的消息能够唯一重建有效括号序列的概率，模 $998244353$。

()()

249561089

解释 #1

对于第一个示例，只有当第二个字符和第三个字符都没有丢失时，鲍勃收到的消息才能唯一重建有效括号序列。发生此事件的概率为 $\frac{3}{4} = 249 561 089 \mod 998 244 353$。

((()(()())))

936828929

()(()(()))

826671105