Dynamic Tiling on a 2-Row Floor

Eustace is investigating the number of different tiling arrangements possible on a 2-row floor over a specified contiguous set of columns. The floor is divided into 2 rows and n columns. Each cell is initially colored either white (W) or black (B). Due to mold issues, the color of a cell can flip (from white to black, or black to white). A tiling arrangement is obtained by optionally placing domino‐shaped tiles on the floor. A domino covers exactly two adjacent cells. Each domino can be placed in one of two ways:

• Vertical placement: Covering both cells in the same column, which is only allowed if the two cells in that column have the same color.
• Horizontal placement: Covering two adjacent cells in the same row across two consecutive columns, which is allowed only if the two cells (one in the current column and one in the next column) have the same color.

You are allowed to leave any cell untiled and domino placements cannot overlap. Two tiling arrangements are considered different if there exists any pair of cells for which in one arrangement the two cells are covered by the same domino while in the other they are not.

More formally, you need to answer two types of queries:

1. Flip the color of a given cell. (If it is white, it becomes black; if it is black, it becomes white.)
2. Given two column indices \(a\) and \(b\) (with \(1 \le a \le b \le n\)), compute the number of different tiling arrangements in the region from column \(a\) to column \(b\) (covering both rows), modulo \(10^9+7\). In this count, an arrangement where no domino is placed is also valid.

Note: When placing a horizontal domino in column \(i\) (covering one cell in column \(i\) and the same-row cell in column \(i+1\)), it is only allowed if the two cells have the same color. Also, if \(i = b\) (i.e. the last column in the query), horizontal placements are not allowed as there is no column \(b+1\) in the region.

All computed arrangement counts must be taken modulo \(10^9+7\).

inputFormat

The first line contains two integers \(n\) and \(q\) \((1 \le n, q \le 10^5)\), representing the number of columns and the number of queries, respectively.

The next two lines each contain a string of length \(n\). The first string represents the colors in row 1 and the second string represents the colors in row 2. Each character is either 'W' or 'B', representing white and black respectively.

Each of the following \(q\) lines contains a query in one of the following two formats:

• 1 r c: Flip the color of the cell in row \(r\) and column \(c\) \((r = 1 \text{ or } 2, 1 \le c \le n)\).
• 2 a b: Query the number of tiling arrangements in the region from column \(a\) to column \(b\) \((1 \le a \le b \le n)\).

outputFormat

For each query of type 2, output a single line containing one integer: the number of tiling arrangements for the specified region modulo \(10^9+7\).

sample

3 3
WWW
WWW
2 1 3
1 1 2
2 1 3

18
11