绵羊 Eustace 最近搬进了新家，他决定翻新他的洗手间，因为他实在无法忍受其单调沉闷的内饰。目前，洗手间的地板由一个 $3 \times N$ 的黑白方格网格组成，具有某种初始图案。

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

唉，Eustace 浴室的顺利翻新取决于他的承包商是否有空，而承包商单方面推迟了他们的计划。在发呆时，Eustace 惆怅地凝视着他浴室地板上从第 $a$ 列到第 $b$ 列的一段区域，心想如果在这个区域内放置部分瓷砖或不放瓷砖，他能组合出多少种不同的图案。如果两种图案中，在一种图案里共享同一块瓷砖的两个方格在另一种图案里没有共享同一块瓷砖，则认为这两种图案是不同的。

就在他刚刚算完可能图案的总数时，他意识到由于霉菌、潮湿等各种因素，一些方格已经变色了。具体来说，有时位于第 $x$ 行第 $y$ 列的单个方格的颜色可能会发生翻转（从黑色变为白色，反之亦然）。

帮助 Eustace 在浴室地板颜色不断变化的情况下，确定可能放置瓷砖的图案数量，以此来回答他的问题！

由于答案可能很大，请输出答案模 $1\,000\,000\,007$ 的余数。

输入格式

你的程序必须从标准输入中读取。

输入的第一行包含两个整数 $N$ 和 $Q$，分别表示 Eustace 浴室地板的长度以及查询和更新的总数。

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

接下来有 $Q$ 行，每行采用以下格式之一：

• 1 x y：表示一次更新，将第 $x$ 行第 $y$ 列的方格颜色进行翻转。
• 2 a b：表示一次查询，询问如果瓷砖仅限于放置在第 $a$ 列到第 $b$ 列之间，可以形成多少种图案。不放置任何瓷砖也算作一种图案。

输出格式

你的程序必须输出到标准输出。

对于每个查询，在新的一行中输出可能图案数量模 $1\,000\,000\,007$ 的余数。

实现细节

由于子任务 2 和 4 的输入长度可能非常大，建议您使用带有快速输入例程的 C++ 来解决此问题。科学委员会没有使用 Java 或 Python 编写的能够完全解决此问题的方案。

附件中提供了包含快速输入/输出模板的 C++ 和 Java 源文件。强烈建议您使用这些模板。

如果您使用 Java 实现解决方案，请将文件命名为 Tiles.java，并将主函数放在 Tiles 类中。

子任务

每个测试用例的最大执行时间为 4.0 秒，最大内存使用量为 1GiB。对于所有测试用例，输入将满足以下范围：

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

您的程序将在满足以下限制的输入实例上进行测试：

样例

输入样例 1

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

输出样例 1

11
3
3
1

说明 1

使用 -- 表示一块瓷砖，第一次查询的 11 种图案为：

.x.x   .x.x   .x.x   .x.x
xx..   xx..   xx--   xx|.
...x   .--x   --.x   ..|x

.x.x   .x.x   .x|x   .x|x
xx..   xx--   xx|.   xx|.
--.x   .--x   .--x   ...x

.x.x   .x.x   .x|x
xx--   xx|.   xx|.
...x   --|x   --.x

对于第二次查询，瓷砖仅限于第 3 列。这 3 种图案为：

.   .   |
.   |   |
.   |   .

在第一次更新后，浴室地板将如下所示：

.x.x
xxx.
...x

现在第三次查询只有 3 种可能的图案：

.x.x   .x.x   .x.x
xxx.   xxx.   xxx.
...x   --.x   .--x

对于最后一次查询，不能单独在第 3 列放置任何瓷砖。只有一种图案，即当前不放瓷砖的图案。

输入样例 2

2 1
..
..
xx
2 1 2

输出样例 2

7

说明 2

使用 -- 表示一块瓷砖，这 7 种图案为：

..   ..   .|   --   |.   --   ||
..   --   .|   ..   |.   --   ||

输入样例 3

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

输出样例 3

47177097
254767228