题目描述

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

热离子有三种类型，分别用红色、绿色和蓝色表示。这些名称与粒子的真实颜色或光的波长无关，只是 Bynstein 教授用不同颜色的马克笔来标记它们。

红色和绿色热离子可以发生反应，但只能与另一个相同颜色的粒子反应：

• 两个红色热离子碰撞时，会产生一个绿色热离子，并释放 $1$ 字节焦耳的能量；
• 两个绿色热离子碰撞时，会产生一个红色热离子，并释放 $1$ 字节焦耳的能量。

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

教授准备进行一次受控反应实验。他在实验室中准备了排成一排的 $n$ 个热离子。几天后，他会把这些热离子带到正在首都地下建造的大型热离子对撞机中。到那时，所有蓝色热离子都已经变成红色或绿色热离子。

在对撞实验中，教授希望进行一系列反应，使总共释放 $n-1$ 字节焦耳的能量，并且最后只剩下一个热离子。每次反应可以选择相邻的两个热离子。反应生成的新热离子会与其左侧和右侧的热离子相邻，并可以继续参与后续反应。

现在的问题是：当所有蓝色热离子都发生变化后，有多少种变化方式能使完整反应序列成功进行下去。

你的任务是计算这样的蓝色热离子变化方式数量，并对 $10^9+7$ 取模。此外，教授还会多次修改实验室中某个位置的热离子类型；每次修改后，也需要重新输出答案。

输入格式

第一行包含两个整数 $n$ 和 $q$，分别表示热离子个数和修改次数。

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

接下来 $q$ 行，每行包含一个整数 $k_i$ 和一个字符（C、Z 或 N），表示第 $i$ 次修改中，教授将第 $k_i$ 个粒子换成该字符表示的类型。

输出格式

输出 $q+1$ 行。

第 $i+1$ 行输出一个整数，表示经过前 $i$ 次修改后的答案。

也就是说，需要输出蓝色热离子有多少种变化方式，使得最终能够完成反应、释放 $n-1$ 字节焦耳能量，并只剩下一个热离子。答案对 $10^9+7$ 取模。

样例一

输入

5 3
NNCCZ
3 N
2 Z
1 Z

输出

3
5
3
1

限制与约定

对于 $100\%$ 的数据，满足：

$$1\le n\le 2\times 10^5,\quad 0\le q\le 10^5,\quad 1\le k_i\le n.$$

子任务	额外限制
1	$n\le 20, q\le 20$
2	$n\le 100, q\le 100$
3	$n\le 10000, q\le 5000$
4	$n\le 30000, q\le 20000$
5	$n\le 10^5, q\le 50000$
6～10	$n\le 2\times 10^5, q\le 10^5$