题目背景

Eustace the Sheep 刚搬进新家，决定翻新他的浴室，因为他实在受不了它单调的内部装饰。目前，浴室的地板是一个 $3 \times N$ 的黑白方格网格。

他有大量相同的 $1 \times 2$ 长方形瓷砖。为了保持浴室的美观，瓷砖可以旋转，但必须平行于墙壁摆放。此外，粘贴瓷砖的胶水不能涂在黑色方格上，因此瓷砖只能放在白色方格上。

题目描述

Eustace 想知道，在从第 $a$ 列到第 $b$ 列的区域中，可以形成多少种不同的瓷砖铺设方案（可以不铺瓷砖）。如果两种方案中，某两个方格是否共用一块瓷砖不同，则认为两种方案不同。

在计算铺设方案的同时，Eustace 注意到由于霉菌等问题，部分方格可能会变色（从黑变白，或从白变黑）。

请帮助 Eustace 在不断变化的地板颜色中回答以下问题：

1. 翻转某个方格的颜色。
2. 查询特定区域内可能的瓷砖铺设方案数。

输出结果需要对 $10^9 + 7$ 取模。

输入格式

• 第一行包含两个整数 $N$ 和 $Q$，表示浴室地板的列数以及查询和更新操作的总数。
• 接下来 $3$ 行，每行包含一个长度为 $N$ 的字符串，仅由 . 和 x 组成：
  • . 表示白色方格。
  • x 表示黑色方格。
• 接下来的 $Q$ 行中，每行有两种格式之一：
  • 1 x y：表示翻转第 $x$ 行第 $y$ 列的方格颜色。
  • 2 a b：查询从第 $a$ 列到第 $b$ 列可能的铺设方案数。

输出格式

对于每个查询操作（格式为 2 a b），输出一个整数表示方案数对 $10^9 + 7$ 取模后的结果。

4 5
.x.x
xx..
...x
2 1 4
2 3 3
1 2 3
2 1 4
2 3 3

11
3
3
1

2 1
..
..
xx
2 1 2

7

14 2
..............
..............
..............
2 2 11
2 1 14

4717709
254767228

提示

【样例解释】

• 对于样例 $1$，在第一次查询时，可以形成 $11$ 种铺设方案。
• 在更新操作后，某些区域的方格颜色发生变化，导致后续查询结果也发生改变。

【数据范围】

• $1 \leq N, Q \leq 30000$
• $1 \leq x \leq 3$
• $1 \leq y \leq N$
• $1 \leq a \leq b \leq N$