You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

T4 字符替换（replace）

题目描述

给定一个仅包含 0、1、2、a、b、c 和 ? 的字符串，你需要将字符串中的每个 ? 分别替换成 0 或 1 或 2 之一，将字符串中的每个 a 分别替换成 0 或 1 之一，将字符串中的每个 b 分别替换成 0 或 2 之一，将字符串中的每个 c 分别替换成 1 或 2 之一。也就是说替换成一个 $012$ 字符串。特别地，如果字符串中不包含 ?，应将其自身视为唯一的替换方案。

求有多少种替换方案，使得替换后的字符串满足：恰好拥有奇数个“好的”非空子串。“好的”的定义为其本质不同的子序列（包含空集）个数为奇数。

每个数据点会给定一个字符串 $s$ ，然后每次对 $s$ 的一个子串进行询问，答案对 $998244353$ 取模。

输入格式

第一行一个整数 $n$。

第二行一个长为 $n$ 的字符串 $s$，仅包含 0、1、2、a、b、c 和 ?。

第三行一个整数 $m$ 表示询问次数。

接下来 $m$ 行，每行两个整数 $l,r$ 表示对子串 $s_{l,r}$ 进行一次询问。

输出格式

$m$ 行，每行一个正整数表示答案，对 $998244353$ 取模。

样例1

样例输入

5
100a1
5
1 5
1 4
2 5
3 4
1 3

样例输出

1
0
1
1
1

样例解释

对于【样例#1】的第一个询问 1 5，有 $2$ 种替换方案，分别为字符串 10001 和 10011。

其中 10001 有 $3$ 个子串为好的，满足不同的子序列的个数为奇数：10001，拥有 $15$ 个不同的子序列；$s'_ {2,3}$ 和 $s'_ {3,4}$ 均为 00，都拥有 $3$ 个不同的子序列。

而 10011 则拥有 $4$ 个子串为好的，满足不同的子序列的个数为奇数，分别为 1001、00、0011、11。

10001 有奇数个好的子串，因此计入答案；而 10011 有偶数个好的子串，因此不计入答案。

样例2

样例输入

20
1110aa01001010a1a110
20
1 20
5 16
11 16
10 13
5 14
13 17
1 18
1 7
6 9
15 19
12 17
17 18
4 11
3 13
13 15
18 19
2 8
7 13
4 15
9 18

样例输出

3
2
2
0
4
2
13
3
0
1
3
1
2
2
2
1
2
1
1
3

样例解释

对于【样例#2】的第一个询问 1 20，$s_{1,20}$ 有 $4$ 个 a，因此有 $2^4=16$ 种替换方案。

样例3

样例输入

10
a11bcabab2
10
7 8
2 8
5 8
3 9
4 8
6 6
1 10
3 7
2 4
1 4

样例输出

1
26
9
48
7
0
54
5
2
1

数据范围

对于 $100\%$ 的数据，满足 $1\leq n\leq 5\times10^4,1\leq m\leq10^6$ 。