P5565 [Celeste-B] Farewell to Mount Celeste

> Sever the Skyline > Black Moonrise > Good Karma > Golden Feather > Mirror Magic > Center of the Earth > No More Running > And... > Say Goodbye.

在分别的宴会上，朋友们拿出他们把多彩的珠子串成的彩色的项链。 项链在夕阳的余晖里闪闪发光，仔细一看，项链周围竟然已经聚集了许多鸟儿，鸟儿们带着 Madeline 与她的朋友们来到了一处他们不曾来过的地方，这里汇聚着好大一群鸟，似乎想要向他们表达些什么。 经过 Madeline 仔细地观察，它发现一些鸟儿们飞动的方式好像排成了一个有序的式子，而另一些鸟儿飞动的方式则是一些符号，符号表达着一个问题。 鸟儿们表达的问题是这样的： 鸟儿们组成的式子会由 `(`,`)`,`^`,`&`,`|`,`0`,`1` 和小写字母构成，并且是一个表达式。 其中： - `(`,`)` 表示括号，在括号中的运算优先级提高。 - `&`,`|`,`^` 表示 `与`,`或`,`异或` 三种位运算，这三种运算**优先级相同** - `0`,`1` 即为 `0`,`1` - 小写字母表示变量，多次出现的同一小写字母表示**不同**的变量，一个变量取值 `0` 或 `1` - 表达式的定义如下： - 一个变量,`0`,`1` 均为表达式 - 若 $T$ 是表达式，则 $(T)$ 是表达式 - 若 $S$,$T$ 是表达式，则$S\&T$,$S|T$,$S\ \hat{}\ T$均为表达式 - 例如，$(1\ \hat{}\ 1\&0)$ 是一个表达式，并且运算结果为 $0$，但 $(1\&0$ 不是一个表达式 鸟儿们认为，要能算出 $1$ 的表达式才是优美的，定义一个表达式的优美度为在这个表达式所有 $v$ 个变量的 $2^v$ 种取值中能算出 $1$ 的方案数。 鸟儿们还认为，一个表达式的和谐度是这个表达式的所有**子连续表达式**的优美度的和。(包含自身) 鸟儿们还是善变的，它们会时不时改变一个位置的字符，但是它们向 Madeline 和她的朋友们保证它们不会改变括号，并且进行修改之后整个串仍然是一个表达式。 你能帮助 Madeline 和她的朋友们算出每次修改后整个表达式的和谐度吗？ 鸟儿们还说，因为表达式可能太和谐了，因此 Madeline 可以只回答和谐度对 $998244353$ 取模后的值。

第一行为一个数 $m$ ,表示修改数 第二行为一个字符串，表示初始表达式 之后 $m$ 行，每一行一个数 $a$ 和一个字符 $b$ ，表示鸟儿们将 $a$ 位置字符变成 $b$ 在输入的表达式中，一个小写字母代表一个变量。(注意一个字母可能出现多次，但代表**不同**变量)

$m$ 行，第 $i$ 行为第 $i$ 次修改后的权值。由于和谐度可能很大，你需要对 $998244353$ 取模。

设 $n$ 为表达式中变量和 $0,1$ 的个数，$len$ 为表达式长度 有subtask 对于 $ 5\% $ 的数据, $ n \leq 12 , len \leq 50 , m \leq 50 $,1s 对于额外 $ 10\% $ 的数据, $ n \leq 150,len \leq 400,m \leq 200$ 对于额外 $ 10\% $ 的数据, $ n \leq 10^5,len \leq 2\times 10^5,m \leq 10$ ,没有括号 对于额外 $ 10\% $ 的数据, $ n \leq 10^5,len \leq 2\times 10^5,m \leq 10^5 $ ,没有括号 对于前 $ 50\% $ 的数据, $ n \leq 10^5,len \leq 4\times 10^5,m \leq 10^5 $ ,保证括号随机生成 对于 $ 100\% $ 的数据, $ n \leq 10^5,len \leq 4\times 10^5,m \leq 10^5 ,len-2\times n \leq 2 \times 10^5$ 对于后 $ 95\% $ 的数据，时限为3s