解题思路

给定一个上界 $n$（以二进制字符串给出）和 $m$ 条限制。每条限制为一对 $(p,o)$，表示：把 $x$ 写成二进制（最低位下标从 0 计），则从低位起的第 $p$ 位必须等于 $o\in\{0,1\}$。问区间 $[0,n]$ 内满足所有限制的整数个数，答案对 $998244353$ 取模。

关键观察：

1. 若某个位置被要求既为 0 又为 1，或某条限制要求在 $p\ge L$（$L=\text{len}(n)$）的高位为 1，则不可能，答案为 0。因为对所有 $x\le n$，在第 $p(\ge L)$ 位一定为 0。
2. 将限制先映射到长度为 $L$ 的数组 need[i]（下标从高位到低位）。 输入的 $p$ 是从低位计数，换算为从高位的下标：i = L-1-p。若 i<0 或 i>=L 则是上面的越界情况。
3. 在长度为 $L$ 的二进制位上做“数位 DP”（Digit DP，二进制版本）：从最高位向最低位扫描，维护是否“已严格小于 $n$”的状态。

题目内容

给定一个正整数 $n$ ，你需要计算有多少个非负整数 $x∈[0,n]$ 且满足给定的所有 $m$ 条限制。

每一条限制形如：将 $x$ 表示成二进制，某一位必须是 $0/$ 必须是 $1$ 。

输入描述

第一行描述 $n$ 。本题中，$n$ 可能很大(详见数据规模)，所以 $n$ 会以二进制表示法给出。例如，若 $n=11$ ，则输入为 $1011$ 。保证输入的二进制电不含前导 $0$ 。

第二行一个正整数 $m$ ，表示限制条数。

接下来 $m$ 行，每一行两个整数 $p,o(0≤p≤[log_2n]+1,o∈${$0,1$}$)$，描述一条限制：若将 $x$ 表示成二进制，则从低位起的第 $p$ 位必须是 $o$ 。

注意，我们约定最低位下标从 $0$ 开始，例如，对于二进制数 $1011$ ，从低位起的第 $0$ 位是 $1$ ，第 $1$ 位是 $1$ ，第 $2$ 位是 $0$ ，第 $3$ 位是 $1$ 。$1≤n≤2^{2*10^5},1≤m≤2*10^5$

输出描述

输出一行一个整数，表示满足所有限制的 $x$ 的个数。

因为答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。

样例1

输入

1011
2
1 1
3 0

输出

4

说明

满足条件的 $x$ 有：$2,3,6$ 和 $7$ 。它们写成二进制分别为 $(0010)_2,(0011)_2,(0110)_2$ 和 $(0111)_2$ 。

样例2

输入

110011
3
0 0
2 0
4 1

输出

6