We refer “a possible substring of a string obtained by replacing each occurrence of ? in $S$ by 0 or 1 independently” to simply “a string obtained from $S$.” For simplicity, here we assume that an empty string can also be obtained from $S$ too.

For the string $S = s_1s_2\ldots s_N$, for each $i = 0, 1, \ldots, N$, let

• $\mathrm{dp}[i][0] :=$ (the number of strings obtained from the first $i$ character of $S$, $s_1s_2\ldots s_i$, ending with 0);
• $\mathrm{dp}[i][1] :=$ (the number of strings obtained from the first $i$ character of $S$, $s_1s_2\ldots s_i$, ending with 1).

Then, the value that should be printed for each query is $\mathrm{dp}[N][0] + \mathrm{dp}[N][1]$ for $S$ at each moment. We will consider how to compute this.

First, obviously, $\mathrm{dp}[0][0] = \mathrm{dp}[0][1] = 0$. We will now consider, for $i = 1, 2, \ldots, N$, “how to find $\mathrm{dp}[i][0]$ and $\mathrm{dp}[i][1]$ when we know $\mathrm{dp}[i-1][0]$ and $\mathrm{dp}[i-1][1]$.”

We first consider $s_i =$ 0. Any string obtained from $s_1s_2\ldots s_{i-1}$ can be obviously obtained from $s_1s_2\ldots s_i$ too. Any string that cannot be obtained from $s_1s_2\ldots s_{i-1}$ that can be obtained from $s_1s_2\ldots s_{i-1} s_i$ by appending $s_i =$ 0 is

a concatenation of a string obtained from $s_1s_2\ldots s_{i-1}$ and 0, that cannot be obtained from $s_1s_2\ldots s_{i-1}$.

The number of “strings that are concatenations of a string obtained from $s_1s_2\ldots s_{i-1}$ and 0” is equal to the number of strings that can be obtained from $s_1s_2\ldots s_{i-1}$, which is expressed as $\mathrm{dp}[i-1][0] + \mathrm{dp}[i-1][1] + 1$ (where the last term $1$ correspond to an empty string) The number of strings that “can be obtained from $s_1s_2\ldots s_{i-1}$” is $\mathrm{dp}[i-1][0]$ (any string $t_1 t_2 \ldots t_l$ ending with 0 that can be obtained from $s_1s_2\ldots s_{i-1}$ can be constructed as a concatenation of $t_1 t_2 \ldots t_{l-1}$, which can be obtained from $s_1s_2\ldots s_{i-1}$, and 0).

Therefore, by appending $s_i =$ 0 to the tail of $s_1s_2\ldots s_{i-1}$, there are $\mathrm{dp}[i-1][1] + 1$ new strings ending with 0 obtained not from $s_1s_2\ldots s_{i-1}$ but from $s_1s_2\ldots s_{i-1} s_i$.

Therefore, when $s_i =$ 0,

• $\mathrm{dp}[i][0] = \mathrm{dp}[i-1][0] + (\mathrm{dp}[i-1][1] + 1)$,
• $\mathrm{dp}[i][1] = \mathrm{dp}[i-1][1]$.

Similarly, when $s_i =$ 1,

• $\mathrm{dp}[i][0] = \mathrm{dp}[i-1][0]$,
• $\mathrm{dp}[i][1] = \mathrm{dp}[i-1][1] + (\mathrm{dp}[i-1][0] + 1)$,

and when $s_i =$ ?,

• $\mathrm{dp}[i][0] = \mathrm{dp}[i-1][0] + (\mathrm{dp}[i-1][1] + 1)$
• $\mathrm{dp}[i][1] = \mathrm{dp}[i-1][1] + (\mathrm{dp}[i-1][0] + 1)$

Therefore, let

$$\mathbf{A}_0 := \left[\begin{matrix} 1 & 1 & 1 \\ 0 & 1 & 0\\ 0 & 0 & 1 \\ \end{matrix}\right], \mathbf{A}_1 := \left[\begin{matrix} 1 & 0 & 0 \\ 1 & 1 & 1\\ 0 & 0 & 1 \\ \end{matrix}\right], \mathbf{A}_? := \left[\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1\\ 0 & 0 & 1 \\ \end{matrix}\right],$$

then for each $i = 1, 2, \ldots, N$ we have

$$\left[\begin{matrix} \mathrm{dp}[i][0]\\ \mathrm{dp}[i][1]\\ 1 \\ \end{matrix}\right] = \mathbf{A}_{s_i} \left[\begin{matrix} \mathrm{dp}[i-1][0]\\ \mathrm{dp}[i-1][1]\\ 1 \\ \end{matrix}\right].$$

Especially,

$$\left[\begin{matrix} \mathrm{dp}[N][0]\\ \mathrm{dp}[N][1]\\ 1 \\ \end{matrix}\right] = \mathbf{A}_{s_N}\mathbf{A}_{s_{N-1}}\cdots \mathbf{A}_{s_1}\left[\begin{matrix} \mathrm{dp}[0][0]\\ \mathrm{dp}[0][1]\\ 1 \\ \end{matrix}\right] = \mathbf{A}_{s_N}\mathbf{A}_{s_{N-1}}\cdots \mathbf{A}_{s_1}\left[\begin{matrix} 0\\ 0\\ 1 \\ \end{matrix}\right].$$

Therefore, each query can be processed by computing the product of $N$ matrices $\mathbf{A}_{s_N}\mathbf{A}_{s_{N-1}}\cdots \mathbf{A}_{s_1}$, and updating one of $\mathbf{A}_{s_N}, \mathbf{A}_{s_{N-1}}, \ldots, \mathbf{A}_{s_1}$ to another matrix. This can be achieved with a segment tree in an $\mathrm{O}(\log N)$ time for each query.

Therefore, the problem has been solved in a total of $\mathrm{O}(N + Q\log N)$ time.