타일

양 Eustace는 새 집으로 이사한 뒤, 칙칙한 화장실 내부를 도저히 참을 수 없어 개조하기로 했다. 현재 변기 바닥은 검은 칸과 흰 칸으로 이루어진 3 × N 격자이며, 초기 배치는 정해져 있다.

Eustace는 크기가 1 × 2인 동일한 직사각형 타일을 매우 많이 가지고 있다. 화장실의 미관을 유지하기 위해 각 타일은 회전할 수 있지만, 변기의 벽과 평행하게 놓아야 한다. 또한 타일을 고정하는 접착제는 검은 칸에는 칠할 수 없으므로, 타일은 흰 칸에만 놓을 수 있다.

안타깝게도 Eustace의 화장실 개조는 시공자의 일정에 달려 있는데, 시공자는 일방적으로 계획을 미뤘다. 멍하니 있던 Eustace는 화장실 바닥의 a번째 열부터 b번째 열까지의 구간을 바라보며, 그 구간 안에 타일을 몇 개 놓거나 하나도 놓지 않아 만들 수 있는 서로 다른 배치의 수가 얼마인지 궁금해한다. 두 배치에서 어떤 타일을 공유하는 두 칸이 서로 다르면 두 배치는 다른 것으로 본다.

가능한 배치의 총수를 막 계산했을 때, 곰팡이와 같은 여러 원인으로 일부 칸의 색이 바뀌었다는 사실을 깨달았다. 특히 x번째 행, y번째 열의 한 칸이 검은색에서 흰색으로, 또는 그 반대로 바뀔 수 있다.

끊임없이 변하는 화장실 바닥의 색 배치 속에서 가능한 타일 배치의 수를 구해 Eustace를 도와주자!

답이 클 수 있으므로, 답을 1 000 000 007로 나눈 나머지를 출력한다.

프로그램은 표준 입력에서 입력을 읽어야 한다.

입력의 첫째 줄에는 Eustace의 화장실 바닥 길이 N과 전체 질의 및 갱신의 수 Q를 나타내는 정수 2개가 주어진다.

이어서 칸의 초기 배치를 나타내는 3개의 줄이 주어진다. 각 줄은 점 ‘.’과 엑스 ‘x’로만 이루어진 길이 N의 문자열이다. 점은 흰 칸, 엑스는 검은 칸을 나타낸다.

그다음 Q개의 줄이 주어지며, 각 줄은 다음 두 형태 중 하나이다.

• 1 x y: x번째 행, y번째 열의 칸 색이 뒤집히는 갱신을 나타낸다.
• 2 a b: 타일을 a번째 열부터 b번째 열까지만 놓을 수 있을 때 만들 수 있는 배치의 수를 묻는 질의이다. 타일을 하나도 놓지 않는 것도 하나의 배치이다.

프로그램은 표준 출력에 출력해야 한다.

각 질의마다 가능한 배치의 수를 1 000 000 007로 나눈 나머지를 새로운 줄에 출력한다.

• 1 ≤ N, Q ≤ 30000
• 1 ≤ x ≤ 3
• 1 ≤ y ≤ N
• 1 ≤ a ≤ b ≤ N