#4010. [ABC 246] Ex. 01? Queries

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Reqwey

题目描述

给你一个长度为 的字符串 ,仅由 01? 三种字符组成。

给你 组询问形如 ,满足 01?

对于第 个询问,你要做出如下操作:

  1. 从左往右数第 个字符改为
  2. 输出满足条件的字符串 的个数 (对 取模),当 中的每个 ? 替换成 01 后,子序列

子序列是指由原串中任意个不一定连续,但保持原有先后顺序的字符构成的字符串。

输入格式

  • 第一行两个整数 ,以一个空格隔开。
  • 第二行为字符串
  • 行中,第 行有两个整数 ,以一个空格隔开。

输出格式

行,第 行为满足条件的字符串数量

样例

样例输入 1

3 3
100
2 1
2 ?
3 ?

样例输出 1

5
7
10

样例解释 1

  1. 个查询从将 更改为 110 开始。有 个字符串可以作为 110 的子序列:011011110。因此,第 个查询应回答
  2. 个查询从将 更改为 1?0 开始。 可转变为 个字符串:100110。有 个字符串可以作为以上字符串之一的子序列:01001011100110。因此,第 个查询应回答
  3. 个查询从将 更改为 1?? 开始。 可转变为 个字符串:100101110111。有 个字符串可以作为以上字符串之一的子序列:0100011011100101110111。因此,第 个查询应回答

样例输入 2

40 10
011?0??001??10?0??0?0?1?11?1?00?11??0?01
5 0
2 ?
30 ?
7 1
11 1
3 1
25 1
40 0
12 1
18 1

样例输出 2

746884092
532460539
299568633
541985786
217532539
217532539
217532539
573323772
483176957
236273405

数据范围与提示

  • 均为整数
  • ,仅由 01? 三种字符组成。
  • 01?