题目描述

题目译自 PA 2022 Runda 1 Wielki Zderzacz Termionów

Albert Bynstein 教授发现了一种新的基本粒子：热离子。如果他的实验成功，就可以在他的帮助下修建一个发电站，这样就可以解决 Byteland 的能源问题了。

这些粒子有三种类型，用红色，绿色和蓝色表示。这个名称与粒子实际的颜色或者光的波长无关，只是 Bynstein 教授用这些颜色的马克笔标记这些粒子。

红色和绿色的热离子可以发生反应，但只与另一个相同颜色的粒子发生反应。当两个红色热离子碰撞时，产生一个绿色热离子，并释放 $1$ 字节焦耳的能量。如果两个绿色热离子发生碰撞，就会产生一个红色热离子，同时释放 $1$ 字节焦耳的能量。

蓝色热离子不与其他热离子反应，但是它们是不稳定的。产生蓝热离子 $72$ 小时后，它会随机变成红热离子或绿热离子中的一个，变成任何离子都不会释放能量。

教授正在准备一个受控的实验反应。为此，他在实验室里准备了排成一排的 $n$ 个热离子。几天后，他打算把这些离子带到目前正在首都地下建造的大型热离子对撞机。到那时，所有的蓝色热离子都将变成红色或绿色热离子。

在对撞实验中，教授想进行一连串的反应，以产生 $n-1$ 字节焦耳的能量，并最后只留下一个热离子。每次反应可以选择相邻的两个热离子。所产生的热离子与左边和右边的热离子相邻，并能与它们发生进一步的反应。

问题是，当所有的蓝色热离子都发生变化时，有多大概率存在一个可行的反应序列。

你的任务是计算蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去。

此外，教授还会在他的实验室里对热离子的位置进行改变，每次都把一个热离子换成另一个（也许不会改变其类型）。在每一次这样的变化之后，也要计算出结果。

输入格式

第一行包含两个整数 $n$ 和 $q\ (1\le n\le 200\ 000,0\le q\le 100\ 000)$，分别表示热离子个数和改变次数。

第二行一个长为 $n$ 的字符串，表示初始时热离子的排列情况。字符串只包含 C，Z 和 N 三种字符，分别表示红色，绿色和蓝色热离子。左起第 $k$ 个字符表示第 $k$ 个热离子的颜色。

接下来 $q$ 行表示对上述字符串的修改。每行包含一个数字 $k_i\ (1\le k_i\le n)$ 和一个字符（C，Z 和 N 之一）。表示第 $i$ 步中，教授将第 $k_i$ 个粒子换成了这个字符所表示的新粒子。

输出格式

输出 $q+1$ 行，第 $i+1$ 行输出一个整数，表示经过前 $i\ (0\le i\le q)$ 个修改后的答案。

输出蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去，生成 $n-1$ 字节焦耳能量。

5 3
NNCCZ
3 N
2 Z
1 Z

3
5
3
1

初始粒子情况是 $\texttt{NNCCZ}$。在将其带到对撞机后，两个蓝色粒子可能变成如下 $4$ 种情况：

• $\texttt{CCCCZ}$：这种情况下，进行完整的反应是不可能的。例如我们可以进行如下反应：$\texttt{CCCCZ}\to \texttt{ZCCZ}\to \texttt{ZZZ}\to \texttt{ZC}$。我们只能获得 $3$ 字节焦耳能量，而不是 $4$。由于只有相同颜色的热离子才会反应，因此不会再产生反应了。
• $\texttt{CZCCZ}$：我们可以完整反应：$\texttt{CZCCZ}\to \texttt{CZZZ}\to \texttt{CCZ}\to \texttt{ZZ}\to \texttt{C}$，获得 $4$ 字节焦耳能量。
• $\texttt{ZCCCZ}$：我们可以完整反应：$\texttt{ZCCCZ}\to \texttt{ZCZZ}\to \texttt{ZCC}\to \texttt{ZZ}\to \texttt{C}$，获得 $4$ 字节焦耳能量。
• $\texttt{ZZCCZ}$：我们可以完整反应：$\texttt{ZZCCZ}\to \texttt{ZZZZ}\to \texttt{ZZC}\to \texttt{CC}\to \texttt{Z}$，获得 $4$ 字节焦耳能量。

在这四种可能性中，有三种可以实现完全反应，因此第一行的正确答案是 $3$。

最终版本的粒子序列是 $\texttt{ZZNCZ}$，在这种情况下，只有蓝色粒子变成红色才能完全反应。因此最后一行的正确答案是 $1$。