#214137. 夜里亦始终想念着你 miss

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

• 选择一个位置 （），若位置 上有棋子，位置 上没有，将位置 上的棋子移到位置 上。
• 选择一个位置 （），若位置 上有棋子，位置 上没有，将位置 上的棋子移到位置 上。

定义一个位置集合 是好的，当且仅当可以通过有限次移动棋子使得棋盘上 中的位置上都有棋子，不需要保证 外的位置没有。

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

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

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

第一行，两个正整数 。

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

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

输出 行，每行一个非负整数，第 行表示第 次修改之后的答案。

样例输入 1

6 1
100111
5

样例输出 1

32
8

样例输入 2

20 3
11110001001010111100
19
6
7

样例输出 2

139904
203264
287744
524288

【样例 1 解释】

在修改之前，棋盘为 ，合法的集合 共有 个。

其中一个是 ，因为我们可以进行如下操作：

• 选择 ，将位置 上的棋子移到位置 上。棋盘变为 。
• 选择 ，将位置 上的棋子移到位置 上。棋盘变为 。

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

现在位置 上都有棋子，所以 合法。

在修改之后，棋盘变为 。因为不存在任何两个棋子相邻，所以无法进行操作，那么合法的 是 的所有共 个子集。

【样例 3】

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

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

【样例 4】

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

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

【样例 5】

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

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

【样例 6】

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

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

【样例 7】

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

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

【数据范围】

对于所有测试数据，保证 ，。

::cute-table{tuack}

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