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$ 个修改后的答案。

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

样例一

input

5 3
NNCCZ
3 N
2 Z
1 Z

output

3
5
3
1

限制与约定

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

$1\le n\le 2 \times 10 ^ 5, 0\le q\le 10 ^ 5, 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\sim 10$：$n\le 2\times 10^5,q\le 10^5$。