池塘上有 n 片荷叶,从 1 编号到 n。现在有一棵大小为 n 的有根树 T 描述了这些荷叶的关系。T 的根是 1。
每片荷叶上都有一个符号 \texttt{U} 或者 \texttt{D}。这个符号表示如果青蛙在第 i 片荷叶上,则:
- 若符号是 \texttt{U},则可以跳到 T 上 i 的祖先(不包含自身)。
- 若符号是 \texttt{D},则可以跳到 T 上 i 的子孙(不包含自身)。
定义这棵树对青蛙是友好的,当且仅当青蛙可以从任意一个荷叶 s 开始,跳过所有荷叶至少一次,回到 s。
由于一些原因,一些荷叶上的符号模糊了,记为 \texttt{?} 符号。定义 f(T) 为把每个 \texttt{?} 符号替换成 \texttt{U} 或 \texttt{D} 后,这棵树对青蛙是友好的方案数。
由于一些原因,这些荷叶上的三种符号可能会发生局部变化,有 q 次修改,每次修改让第 x 片荷叶的符号变成 y,你需要在每次修改后和初始时求出 f(T) 对 998244353 取模的结果。