题目背景

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$ 取模。

5
(1&b)
3 |
2 a
3 &
3 ^
4 1

6
8
4
6
4

10
1|a&1&(0&0|1)&1^1^a
1 0
10 1
2 &
1 a
14 ^
4 |
17 0
4 ^
15 a
15 1

29
30
27
35
35
43
35
35
56
35

30
0|0&0^(a&a&(1^0&0^0)^0&1)|0&a|1|(a&a|0|1|0^a&0&a|(a^0&1|a|a)^a|a&0&0)^a
71 1
51 0
57 0
65 &
26 |
5 a
71 a
56 |
4 &
41 ^
52 |
52 ^
59 a
44 0
54 ^
65 &
51 a
36 1
16 ^
1 1
52 ^
2 |
59 0
58 |
37 ^
55 1
10 1
26 ^
18 |
44 0

21323
10686
5360
5360
5360
8469
16277
16277
16277
16277
16277
16277
16277
8223
8253
8253
16354
8359
8385
8394
8394
8394
4262
4262
4262
4262
2430
2430
2430
2430

20
a^1&0^1^1&1&a&1^a|1&a|0&a^a^1^a^0&1^a&a|a|1^0|a|0^1^a|0^0&1&1&a&a|0^0&a&1&a|a&a^a|0^a^a|a^1|a|1^a|0|a^0&0&0|a|a|a^0^1&0^1&a|1&0
8 ^
28 |
100 ^
119 a
40 &
105 1
31 1
125 1
53 1
98 &
98 &
98 &
52 &
2 ^
38 |
6 ^
58 ^
106 |
12 ^
57 1

957521426
957521583
874091659
57281108
57278566
140708493
120472431
120472431
561701787
551192201
551192201
551192201
551120577
551120577
551121853
551121853
551178140
656274015
656274025
656222855

提示

设 $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