题目描述

译自 NOISG 2021 Final T4. Tiles

绵羊尤斯塔斯最近搬进了一栋新房子，他决定翻新卫生间，因为他无法忍受其单调的内部装饰。目前，卫生间地板由一个 $3$ 行 $N$ 列的黑白方格组成，初始图案由黑白方格构成。

尤斯塔斯注意到他有大量相同的 $1 \times 2$ 矩形瓷砖可供使用。为了保持卫生间的美观，每块瓷砖可以旋转，但必须平行于卫生间墙壁放置。此外，他用来固定瓷砖的胶水无法涂在黑色方格上，这意味着瓷砖只能放置在白色方格上。

然而，尤斯塔斯的浴室翻新计划取决于他的承包商能否按时施工，而承包商却单方面推迟了计划。在白日梦中，尤斯塔斯凝视着他浴室地板从第 $a$ 列到第 $b$ 列的区域，思考在该区域内放置部分或不放置瓷砖可以形成多少种不同的图案。如果两个图案中存在某两个方格在一个图案中共享一块瓷砖，而在另一个图案中不共享，则认为这两个图案不同。

就在他计算出可能图案总数时，他发现由于霉菌、霉变等原因，一些方格的颜色发生了变化。具体来说，位于第 $x$ 行第 $y$ 列的单个方格的颜色可能从黑色变为白色，或从白色变为黑色。

帮助尤斯塔斯回答他的问题，确定在浴室地板颜色不断变化的情况下，可能的瓷砖图案数量！

由于答案可能很大，输出答案除以 $1000000007$ 的余数。

输入格式

程序需从标准输入读取数据。

第一行包含两个整数 $N$ 和 $Q$，分别表示尤斯塔斯浴室地板的列数和查询及更新的总数。

接下来的 $3$ 行表示方格的初始图案。每行包含一个长度为 $N$ 的字符串，仅由点号 . 和叉号 x 组成，其中点号表示白色方格，叉号表示黑色方格。

随后 $Q$ 行，每行采用以下两种形式之一：

• $1 \ x \ y$：表示更新操作，位于第 $x$ 行第 $y$ 列的方格颜色被翻转。
• $2 \ a \ b$：表示查询操作，询问在第 $a$ 列到第 $b$ 列的区域内放置瓷砖可形成的图案数量。不放置任何瓷砖也算一种图案。

输出格式

程序需向标准输出输出结果。

对于每个查询，输出一行，包含一个整数，表示可能图案数量除以 $1000000007$ 的余数。

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

使用 -- 表示一块瓷砖，第一个查询的 $11$ 种图案如下：

第二个查询限制瓷砖在第 $3$ 列，可形成的 $3$ 种图案如下：

第一次更新后，浴室地板如下：

第三个查询的 $3$ 种可能图案如下：

最后一个查询中，第 $3$ 列无法单独放置瓷砖，仅有一种图案，即当前图案。

这个样例仅满足子任务 $1, 3, 4$ 的限制。

2 1
..
..
xx
2 1 2

7

使用 -- 表示一块瓷砖，$7$ 种图案如下：

这个样例仅满足子任务 $1, 3, 4$ 的限制。

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

47177097
254767228

这个样例满足子任务 $2, 3, 4$ 的限制。

数据范围与提示

对于所有输入数据，满足：

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

详细子任务附加限制及分值如下表所示：