奏绝
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你拥有一个黑之章和白之章构成的序列，你可以用它进行演奏。

对于一次演奏的区间，如果这个区间的两个端点一个为黑之章，一个为白之章，那么该次演奏将会产生该区间长度的影响值，否则该次演奏影响值为 0。

区间长度定义为左端点到右端点的距离，比如 i 到 i + 1 的距离为 1。

对于 m 次询问，你要求出对于每次询问的区间，你在其所有子区间演奏的影响值的和，结果对  998244353 取模。

输入描述:

第一行一个整数 n,m (1\leq n,m \leq 2\times 10^5)。

接下来一行 01 序列 c_i (c_i\in\{0, 1\}) 表示黑之章白之章的排列顺序，其中 1 表示黑之章，0 表示白之章。

接下来 m 行，每行两个整数 l,r (1\leq l\leq r\leq n)，表示一次询问的区间。

输出描述:

m 行，每行一个整数，表示对于每次询问的答案对 998244353 取模。
示例1

输入

复制 
5 4
01001
1 3
2 5
3 4
1 5

输出

复制 
2
6
0
11