T2 摆烂合唱

题目信息

时间限制: 1s

空间限制: 256M

输入文件: binary.in

输出文件: binary.out

题目描述

二进制合唱是二进制中学每年迎新晚会的必备项目，二进制合唱由 $n$ 位同学和一个合唱队形组成，每位同学只需会唱 0 或 1 两个声调，合唱队形由 $n-1$ 个确定的符号组成，每个符号是 $and, or, xor$ 中的一个，每次合唱的最终声调是由每位同学的声调通过合唱队形，即 $n-1$ 个符号运算得出的。

时过境迁，二进制中学的新同学们越来越聪明，但是越来越喜欢在集体活动中摆烂，因此二进制合唱逐渐演变成每位同学计算 $f$ 函数的一个活动。$f$ 函数的定义如下：对于第 $i$ 位同学，$f(i)$ 表示当除了 $i$ 同学以外所有同学唱出的声调确定时， $i$ 同学唱出的声调为 0 和 1 两种状态下，合唱的最终声调不同的概率。

例如，由两位同学组成的合唱 $x\ or\ y$，有 $f(x)=\frac{1}{2}$，因为当 $y=0$ 时，$x$ 的两种声调会导致最终声调不相等；但当 $y=1$ 时，$x$ 无论唱出什么声调，都无法影响到合唱最终声调的值（最终声调始终为 1）。所以 $x$ 取 0 和取 1 两种状态导致合唱最终声调的值不相等的概率为 $\frac{1}{2}$。

再例如 $x\ xor\ y$，有 $f(x)=1$，因为无论 $y$ 的取值如何，$x$ 的取值不同时，$x\ xor y$ 的值总是不同的。

每位同学都想知道自己的 $f(i)$ 的值，结果对 998244353 取模。大家想在合唱摆烂而争相计算自己的 $f$ 函数，这何尝不是新版本的集体活动呢？

合唱队形由表达式 $Expr$ 组合而成：

1. $Expr$ 可以是一个单独的变量（一位同学唱出的声调）；
2. 否则，$Expr$ 将表示成 $(Expr1\ op\ Expr2)$，其中 $Expr1$ 和 $Expr2$ 分别是表达式，$op$ 是一种运算符，输入保证不会省略任何括号（包括整个表达式外的括号）。

输入格式

第一行一个整数 $n$，表示参与二进制合唱的同学数

第二行一个字符串 $s$，表示给定的合唱队形，格式见题目描述。

在 $s$ 中，不存在空格，用 & 表示 and，用 | 表示 or，用 ^ 表示 xor，用 $\mathrm{x}$ 表示一个同学，保证 $s$ 中恰有 $n-1$ 个符号和 $n$ 个同学，每个符号都有对应的括号限定运算的先后关系（即共有 $n-1$ 对括号）；

输出格式

共 $n$ 行，第 $i$ 行一个整数 $f(i)$，代表给定的合唱队形中从左到右第 $i$ 个同学的 $f$ 值对 998244353 取模的结果。

样例

样例输入 1

4
((x^x)|(x&x))

样例输出 1

249561089
249561089
748683265
748683265

样例解释 1

输出的四个数分别为 $\frac{3}{4}, \frac{3}{4}, \frac{1}{4}, \frac{1}{4}$。

数据范围与提示

对于 $100 \%$ 的数据：$1 \leq n \leq 10^5$，$s$ 是合法的二进制表达式，遵从题目描述和输入格式中的所有规定。

• Subtask 1 (5 pts): $n \leq 1$；
• Subtask 2 (25 pts): $n \leq 16$；
• Subtask 3 (30 pts): $n \leq 10^3$；
• Subtask 4 (40 pts): 无特殊限制。