【题目描述】
这次的任务是探索一处古代遗迹——二叉搜索树。这一遗迹神秘而又危险，但通过 预言/占卜相关能力的队员的帮助，你的知道这一遗迹由无数个洞穴组成，洞穴之间连边 形成了一棵二叉树的形态，每个洞穴都封印着神秘物品，且每个洞穴的左儿子子树中所 有洞穴封印的物品都比自己封印的更加危险，右儿子子树中封印的都比自己封印的更安 全。
因此，你制订了以下探索方案：当一队人前来探索遗迹时，他们会按顺序依次进入 树的根节点，当一位队员来到某个节点时：
• 如果当前节点还没有人，该队员会停在这个节点，以防止此地出现异变影响后续探 索。
• 如果当前节点有人，且对方的序列 ≥ 自己的序列，则该队员会继续走到当前节点 的左儿子节点中进行探索。
• 如果当前节点有人，且对方的序列 < 自己的序列，则该队员会继续走到当前节点 的右儿子节点中进行探索。
所有队员都依次进入后，定义这样一次探索的成功度为所有队员最终停留位置与根 节点的距离的最大值。在遗迹中距离定义为两点之间的简单路径中的点数 −1。
现在，你集结了组织中的 n 位成员，他们排成一列等候调遣，依次编号为 1 ∼ n。但 不幸的是，你不知道他们的序列确切是多少，因为序列 0 具有唯一性，你知道哪些人的 序列为 0，除此之外的人的序列均 ≥ 1。于是你决定派遣编号为 l ∼ r 的成员，按照编号 从小到大排序后进行探索，并粗略的认为这样一次探索的收益为，将所有不确定序列的 队员的序列任意指定为 $ ≤ 114514^{1145141}^{14514}^{...} $ 的正整数时，能获得的探索成功度的最小值。 你将它称为区间 [l, r] 的权值。
于是为了能更好的进行探索，他想询问你——一位占卜家，区间 [x, y] 的所有子区间 的权值之和是多少？当然，一个严谨的队长不会只询问一次，而是会询问 q 次，你都需 要进行回答。
【输入格式】
从文件 mystery.in 中读入数据。
第一行两个非负整数 n, q 分别表示队员的数量以及询问的数量。
第二行是一个长为 n 的 01 串，第 i 位为 0 表示第 i 个队员的序列为 0，为 1 表示 第 i 个队员的序列可能是任意 $ ≤ 114514^{1145141}^{14514}^{...} $ 的正整数。
接下来 q 行，每行两个正整数 l, r ，表示询问区间 [l, r] 的所有子区间的权值之和对 998244353 取模后的结果。
【输出格式】
输出到文件 mystery.out 中。
输出 q 行，第 i 行一个正整数表示第 i 个询问的答案对 998244353 取模后的结果。
【样例 1 输入】

4 4
1011
1 4
2 2
2 3
1 3

8
0
1 
3

特殊性质 A：保证所有队员的序列均不为 0。
特殊性质 B：对于所有询问有 l = 1, r = n。