题目描述

有一个一行 $n$ 列的棋盘，其中有些位置放有一枚棋子。你可以按照以下两种方式移动棋子：

• 选择一个位置 $i$（$1 < i < n$），若位置 $i - 1, i$ 上有棋子，位置 $i + 1$ 上没有，将位置 $i - 1$ 上的棋子移到位置 $i + 1$ 上。
• 选择一个位置 $i$（$1 < i < n$），若位置 $i, i + 1$ 上有棋子，位置 $i - 1$ 上没有，将位置 $i + 1$ 上的棋子移到位置 $i - 1$ 上。

定义一个位置集合 $S \subseteq \{1, 2, \dots, n\}$ 是好的，当且仅当可以通过有限次移动棋子使得棋盘上 $S$ 中的位置上都有棋子，不需要保证 $\boldsymbol{S}$ 外的位置没有。

另外有 $q$ 次修改，每次修改时棋盘上的某个位置的状态会发生改变：

• 若修改之前该位置上存在棋子，棋子将被移除，否则该位置将被放上一枚棋子。

请你在所有修改生效之前，以及每个修改生效之后，都求出好的位置集合的个数对 $10^9 + 7$ 取模的值。

输入格式

第一行，两个正整数 $n, q$。

第二行，一个长度为 $n$ 的 $01$ 串。其中第 $i$ 个字符若为 $1$，表示棋盘上第 $i$ 个位置有棋子；否则表示棋盘上第 $i$ 个位置没有棋子。

接下来 $q$ 行，每行一个正整数 $p$，表示棋盘上第 $p$ 个位置的状态发生改变。

输出格式

输出 $(q + 1)$ 行，每行一个非负整数，第 $i$ 行表示第 $(i - 1)$ 次修改之后的答案。

6 1
100111
5

32
8

20 3
11110001001010111100
19
6
7

139904
203264
287744
524288

提示

【样例 1 解释】

在修改之前，棋盘为 $\texttt{100111}$，合法的集合 $S$ 共有 $32$ 个。

其中一个是 $\{1, 2, 6\}$，因为我们可以进行如下操作：

• 选择 $i = 4$，将位置 $i + 1$ 上的棋子移到位置 $i - 1$ 上。棋盘变为 $\texttt{101101}$。
• 选择 $i = 3$，将位置 $i + 1$ 上的棋子移到位置 $i - 1$ 上。棋盘变为 $\texttt{111001}$。

注意以上操作均为假设，并不会真正地对棋盘进行改动。

现在位置 $1, 2, 6$ 上都有棋子，所以 $S = \{1, 2, 6\}$ 合法。

在修改之后，棋盘变为 $\texttt{100101}$。因为不存在任何两个棋子相邻，所以无法进行操作，那么合法的 $S$ 是 $\{1, 4, 6\}$ 的所有共 $8$ 个子集。

【样例 3】

见附件中的 miss/miss3.in 与 miss/miss3.ans。

该样例满足测试点 $4 \sim 6$ 的约束条件。

【样例 4】

见附件中的 miss/miss4.in 与 miss/miss4.ans。

该样例满足测试点 $13$ 的约束条件。

【样例 5】

见附件中的 miss/miss5.in 与 miss/miss5.ans。

该样例满足测试点 $14 \sim 15$ 的约束条件。

【样例 6】

见附件中的 miss/miss6.in 与 miss/miss6.ans。

该样例满足测试点 $19 \sim 20$ 的约束条件。

【样例 7】

见附件中的 miss/miss7.in 与 miss/miss7.ans。

该样例满足测试点 $21 \sim 25$ 的约束条件。

【数据范围】

对于所有测试数据，保证 $1 \le n \le 5 \times 10^5$，$0 \le q \le 5 \times 10^5$。

::cute-table{tuack}

测试点编号	$n \le$	$q \le$	特殊性质
$1 \sim 3$	$20$	$0$	无
$4 \sim 6$	^	$5 \times 10^5$	^
$7$	$4000$	$0$	有
$8 \sim 9$	^	^	无
$10$		$4000$	有
$11 \sim 12$		^	无
$13$		$5 \times 10^5$	有
$14 \sim 15$		^	无
$16$	$5 \times 10^5$	$0$	有
$17 \sim 18$	^	^	无
$19 \sim 20$		$5 \times 10^5$	有
$21 \sim 25$		^	无

特殊性质：保证棋盘上所有的第奇数个位置始终有棋子。