테르미온 대형 충돌기

알베르트 바이트자인 교수는 새로운 종류의 기본 입자인 테르미온을 발견했다. 실험이 성공하면 테르미온으로 바이토시아의 에너지 문제를 해결할 발전소를 지을 수 있을지도 모른다.

테르미온은 빨강, 초록, 파랑 세 종류가 있다. 이 이름은 입자의 실제 색이나 빛의 진동수와 아무 관련이 없다. 교수가 마침 그 색의 펜을 갖고 있었을 뿐이다.

빨강과 초록 테르미온은 서로 반응할 수 있지만, 같은 색의 다른 테르미온과만 반응한다. 빨강 테르미온 두 개가 충돌하면 초록 테르미온 하나가 생기고 1 바이트줄의 에너지가 나온다. 초록 테르미온 두 개가 충돌하면 빨강 테르미온 하나가 생기고 역시 1 바이트줄의 에너지가 나온다.

파랑 테르미온은 다른 테르미온과 반응하지 않지만 불안정하다. 생산된 지 72시간이 지나면 무작위로 빨강 또는 초록 테르미온으로 바뀐다. 이 변환은 에너지를 쓰거나 만들지 않는다.

교수는 통제된 실험 반응을 준비하고 있다. 연구실에서 테르미온 n개를 한 줄로 늘어놓아 사슬을 만들었다. 며칠 뒤 교수는 이 사슬을 수도 지하에 건설 중인 대형 테르미온 충돌기로 옮길 계획이다. 그때까지 모든 파랑 테르미온은 빨강 또는 초록으로 바뀌어 있다.

충돌기에서 교수는 n-1 바이트줄을 만들고 마지막에 테르미온 하나만 남기는 반응 순서를 실행하려 한다. 각 반응에서는 사슬에서 서로 인접한 두 테르미온이 참여한다. 생긴 테르미온은 왼쪽과 오른쪽 이웃에 이어져 있으며, 이후 반응에도 계속 참여할 수 있다.

파랑 테르미온이 모두 바뀌었을 때 이런 반응 순서를 실행할 수 있는지가 문제다.

과제는 모든 파랑 테르미온이 빨강 또는 초록으로 바뀌는 방법 중, 전체 반응 순서를 실행할 수 있게 하는 방법의 수를 10^9 + 7로 나눈 나머지로 구하는 것이다.

추가로 교수는 연구실에서 사슬을 바꾼다. 매번 테르미온 하나를 다른 것으로 교체하는데, 색이 같을 수도 있다. 이런 변경을 할 때마다 그 뒤의 답도 구하라.

첫 줄에 두 정수 n과 q (1 ≤ n ≤ 200 000, 0 ≤ q ≤ 100 000)가 주어진다. 각각 사슬의 테르미온 수와 변경 횟수이다.

둘째 줄에는 처음 사슬 상태를 나타내는 길이 n의 문자열이 주어진다. 문자 C, Z, N은 각각 빨강, 초록, 파랑 테르미온을 뜻한다. 왼쪽에서 k번째 문자가 왼쪽에서 k번째 테르미온의 색이다.

다음 q개 줄에는 변경이 하나씩 주어진다. 각 줄은 정수 k_i (1 ≤ k_i ≤ n)와 C, Z, N 중 하나의 문자로 이루어진다. 이는 i번째 변경에서 왼쪽에서 k_i번째 테르미온을 해당 색의 새 테르미온으로 바꾼다는 뜻이다.

q + 1개의 줄을 출력한다. i + 1번째 줄에는 i번 변경 후의 사슬에 대한 답을 출력한다 (0 ≤ i ≤ q).

각 답은 그 사슬의 파랑 테르미온이 바뀌는 방법 중, n - 1 바이트줄을 내는 전체 반응 순서를 실행할 수 있게 하는 방법의 수를 10^9 + 7로 나눈 나머지이다.

초기 사슬은 NNCCZ이다. 대형 하드론 충돌기로 가는 길에 두 파랑 테르미온은 4가지 방법으로 바뀔 수 있다.

• CCCCZ. 이 경우 전체 반응 순서는 불가능하다. 예를 들어 CCCCZ에서 ZCCZ, ZZZ, ZC 순으로 진행할 수 있지만, 3 바이트줄만 얻고 같은 색끼리만 반응하므로 더는 진행할 수 없다.
• CZCCZ. CZCCZ, CZZZ, CCZ, ZZ, C 순으로 진행하여 4 바이트줄을 얻는 전체 반응 순서가 가능하다.
• ZCCCZ. ZCCCZ, ZCZZ, ZCC, ZZ, C 순으로 진행하여 4 바이트줄을 얻는 전체 반응 순서가 가능하다.
• ZZCCZ. ZZCCZ, ZZZZ, ZZC, CC, Z 순으로 진행하여 4 바이트줄을 얻는 전체 반응 순서가 가능하다.

네 가지 중 세 가지에서 전체 반응 순서가 가능하므로 첫 번째 답은 3이다.

모든 변경 후의 최종 사슬은 ZZNCZ이다. 전체 반응 순서가 가능한 경우는 파랑 테르미온이 빨강으로 바뀌는 한 가지뿐이므로 마지막 답은 1이다.