[PA 2022] Wielki Zderzacz Termionów

**题目译自 [PA 2022](https://sio2.mimuw.edu.pl/c/pa-2022-1/dashboard/) Runda 1 [Wielki Zderzacz Termionów](https://sio2.mimuw.edu.pl/c/pa-2022-1/p/wzt/)** Albert Bynstein 教授发现了一种新的基本粒子：热离子。如果他的实验成功，就可以在他的帮助下修建一个发电站，这样就可以解决 Byteland 的能源问题了。 这些粒子有三种类型，用红色，绿色和蓝色表示。这个名称与粒子实际的颜色或者光的波长无关，只是 Bynstein 教授用这些颜色的马克笔标记这些粒子。 红色和绿色的热离子可以发生反应，但只与另一个相同颜色的粒子发生反应。当两个红色热离子碰撞时，产生一个绿色热离子，并释放 $1$ 字节焦耳的能量。如果两个绿色热离子发生碰撞，就会产生一个红色热离子，同时释放 $1$ 字节焦耳的能量。 蓝色热离子不与其他热离子反应，但是它们是不稳定的。产生蓝热离子 $72$ 小时后，它会随机变成红热离子或绿热离子中的一个，变成任何离子都不会释放能量。 教授正在准备一个受控的实验反应。为此，他在实验室里准备了排成一排的 $n$ 个热离子。几天后，他打算把这些离子带到目前正在首都地下建造的大型热离子对撞机。到那时，所有的蓝色热离子都将变成红色或绿色热离子。 在对撞实验中，教授想进行一连串的反应，以产生 $n-1$ 字节焦耳的能量，并最后只留下一个热离子。每次反应可以选择相邻的两个热离子。所产生的热离子与左边和右边的热离子相邻，并能与它们发生进一步的反应。 问题是，当所有的蓝色热离子都发生变化时，有多大概率存在一个可行的反应序列。 你的任务是计算蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去。 此外，教授还会在他的实验室里对热离子的位置进行改变，每次都把一个热离子换成另一个（也许不会改变其类型）。在每一次这样的变化之后，也要计算出结果。 ## Input 第一行包含两个整数 $n$ 和 $q$ 分别表示热离子个数和改变次数。 第二行一个长为 $n$ 的字符串，表示初始时热离子的排列情况。字符串只包含 `C`，`Z` 和 `N` 三种字符，分别表示红色，绿色和蓝色热离子。左起第 $k$ 个字符表示第 $k$ 个热离子的颜色。 接下来 $q$ 行表示对上述字符串的修改。每行包含一个数字 $k_i$ 和一个字符（`C`，`Z` 和 `N` 之一）。表示第 $i$ 步中，教授将第 $k_i$ 个粒子换成了这个字符所表示的新粒子。 ## Output 输出 $q+1$ 行，第 $i+1$ 行输出一个整数，表示经过前 $i$ 个修改后的答案。 输出蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去，生成 $n-1$ 字节焦耳能量。 [samples] ## Note 对于 $100\%$ 的数据，满足： $1\le n\le 2 \times 10 ^ 5, 0\le q\le 10 ^ 5, 1\le k_i\le n$。