P11302 [NOISG 2021 Finals] Tiles

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$ 取模后的结果。

【样例解释】 - 对于样例 $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$ | 子任务编号 | 分值 | 额外限制条件 | | :--------: | :--: | :------------------------: | | $1$ | $17$ | $1 \leq N, Q \leq 8$ | | $2$ | $23$ | 不存在黑色方格 | | $3$ | $26$ | $1 \leq N, Q \leq 7000$ | | $4$ | $34$ | 无额外限制 |