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.