{"problem":{"name":"[PA 2022] Wielki Zderzacz Termionów","description":{"content":"**题目译自 [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 教授发现了一种新的基本粒子：热离子。如果他的实验成功，就可以在他","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9252"},"statements":[{"statement_type":"Markdown","content":"**题目译自 [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/)**\n\nAlbert Bynstein 教授发现了一种新的基本粒子：热离子。如果他的实验成功，就可以在他的帮助下修建一个发电站，这样就可以解决 Byteland 的能源问题了。\n\n这些粒子有三种类型，用红色，绿色和蓝色表示。这个名称与粒子实际的颜色或者光的波长无关，只是 Bynstein 教授用这些颜色的马克笔标记这些粒子。\n\n红色和绿色的热离子可以发生反应，但只与另一个相同颜色的粒子发生反应。当两个红色热离子碰撞时，产生一个绿色热离子，并释放 $1$ 字节焦耳的能量。如果两个绿色热离子发生碰撞，就会产生一个红色热离子，同时释放 $1$ 字节焦耳的能量。\n\n蓝色热离子不与其他热离子反应，但是它们是不稳定的。产生蓝热离子 $72$ 小时后，它会随机变成红热离子或绿热离子中的一个，变成任何离子都不会释放能量。\n\n教授正在准备一个受控的实验反应。为此，他在实验室里准备了排成一排的 $n$ 个热离子。几天后，他打算把这些离子带到目前正在首都地下建造的大型热离子对撞机。到那时，所有的蓝色热离子都将变成红色或绿色热离子。\n\n在对撞实验中，教授想进行一连串的反应，以产生 $n-1$ 字节焦耳的能量，并最后只留下一个热离子。每次反应可以选择相邻的两个热离子。所产生的热离子与左边和右边的热离子相邻，并能与它们发生进一步的反应。\n\n问题是，当所有的蓝色热离子都发生变化时，有多大概率存在一个可行的反应序列。\n\n你的任务是计算蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去。\n\n此外，教授还会在他的实验室里对热离子的位置进行改变，每次都把一个热离子换成另一个（也许不会改变其类型）。在每一次这样的变化之后，也要计算出结果。\n\n## Input\n\n第一行包含两个整数 $n$ 和 $q$ 分别表示热离子个数和改变次数。\n\n第二行一个长为 $n$ 的字符串，表示初始时热离子的排列情况。字符串只包含 `C`，`Z` 和 `N` 三种字符，分别表示红色，绿色和蓝色热离子。左起第 $k$ 个字符表示第 $k$ 个热离子的颜色。\n\n接下来 $q$ 行表示对上述字符串的修改。每行包含一个数字 $k_i$ 和一个字符（`C`，`Z` 和 `N` 之一）。表示第 $i$ 步中，教授将第 $k_i$ 个粒子换成了这个字符所表示的新粒子。\n\n## Output\n\n输出 $q+1$ 行，第 $i+1$ 行输出一个整数，表示经过前 $i$ 个修改后的答案。\n\n输出蓝色热离子有多少种变化方式（对 $10^9+7$ 取模）能使完整的反应序列进行下去，生成 $n-1$ 字节焦耳能量。\n\n[samples]\n\n## Note\n\n对于 $100\\%$ 的数据，满足：\n\n$1\\le n\\le 2 \\times 10 ^ 5, 0\\le q\\le 10 ^ 5, 1\\le k_i\\le n$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9252","tags":["2022","PA（波兰）"],"sample_group":[["5 3\nNNCCZ\n3 N\n2 Z\n1 Z\n","3\n5\n3\n1\n"]],"created_at":"2026-03-03 11:09:25"}}