Warehouse Automation Domino Coloring

A warehouse robotics platform models robot movement lanes as domino tiles laid over a 2 x n floor grid. The tiling is handed to you as an array domino of exactly two equal-length strings of English letters: domino[0] is the top row and domino[1] is the bottom row, so cell (r, i) carries the letter domino[r][i].

Every cell of the grid belongs to exactly one domino, and the two rows always describe a complete, non-overlapping tiling. A domino is read off the letters like this:

Vertical domino at column i when domino[0][i] == domino[1][i]. It covers the two cells of that single column.
Horizontal dominoes spanning columns i and i+1 when domino[0][i] != domino[1][i]. There are then two of them stacked: one covering (0, i) and (0, i+1), the other covering (1, i) and (1, i+1). In that case the input is guaranteed to satisfy domino[0][i] == domino[0][i+1] and domino[1][i] == domino[1][i+1].

Two dominoes are adjacent when they share a side — up, down, left or right. Touching only at a corner is not adjacency.

Each domino must be painted with one of three colors: Red, Green or Blue. Both cells of a domino take the same color, and two adjacent dominoes must take different colors.

Count the distinct colorings of the whole tiling in which no two adjacent dominoes share a color, and report that count modulo 10^9 + 7.

Input Format

Two lines.

Line 1: the string domino[0], the top row.
Line 2: the string domino[1], the bottom row.

Both strings have the same length n.

Output Format

Print a single integer — the number of valid colorings, taken modulo 10^9 + 7.

Constraints

1 <= n = |domino[0]| = |domino[1]| <= 99999
Every character of both strings is an English letter, 'a'–'z' or 'A'–'Z'.
The array size is exactly 2 and the two strings have equal length.
The two rows are guaranteed to describe a complete, non-overlapping domino tiling of the 2 x n grid under the two rules above.
No two dominoes that share a side carry the same letter. There are only 52 letters available, so for n > 52 letters must be reused elsewhere in the grid; the tiling is still recovered unambiguously from the two rules above, scanning columns left to right.

Examples

Example 1

Input:

xy
xy

Output:

Explanation: domino[0][0] == domino[1][0] == 'x' and domino[0][1] == domino[1][1] == 'y', so the grid is two vertical dominoes standing side by side. They are adjacent, so the pair must get two different colors: 3 * 2 = 6 colorings — RG, RB, GR, GB, BR, BG.

Example 2

Input:

aacx
ddcx

Output:

Explanation: Columns 0 and 1 hold the horizontal pair a (top) and d (bottom); column 2 holds the vertical c; column 3 holds the vertical x. The pair a/d can be colored in 6 ways. c touches both a and d, which already carry two different colors, so exactly 1 color is left for c. x touches only c, leaving 2 choices. Total 6 1 2 = 12.

Example 3

Input:

abb
acc

Output:

Explanation: a is a vertical domino in column 0; b and c are the horizontal pair over columns 1 and 2. a has 3 choices, and b, c must both differ from a and from each other, so they take the two remaining colors in either order: 3 * 2 = 6. The colorings are [RGG, RBB], [RBB, RGG], [GRR, GBB], [GBB, GRR], [BRR, BGG], [BGG, BRR].

Example 4

Input:

aabb
ccdd

Output:

Explanation: Two stacked horizontal pairs in a row. The first pair a/c admits 6 colorings. Writing the first pair as (x, y) with x != y, the second pair (x', y') needs x' != y', x' != x and y' != y; note x' and y' are free to touch the opposite row's old color, because that contact is only diagonal. Exactly 3 such pairs exist, giving 6 * 3 = 18.

Example 5

Input:

aacceeggiikkmmooqqss
bbddffhhjjllnnpprrtt

Output:

Explanation: Ten stacked horizontal pairs in a row: 6 * 3^9 = 118098.

Example 6

Input:

a
a

Output:

Explanation: A single vertical domino with nothing to conflict with — one free choice out of three.

Notes

The tiling is determined by scanning columns from left to right: at column i, equal letters in the two rows mean a vertical domino and you move on to column i+1; unequal letters mean a stacked horizontal pair and you move on to column i+2.
Both cells of one domino always receive the same color; you are coloring dominoes, not cells.
Diagonal contact is not adjacency. In particular the top domino of one horizontal pair is not adjacent to the bottom domino of the next horizontal pair. (If diagonal contact did count, two consecutive horizontal pairs could never be colored at all and every such grid would answer 0.)
The answer grows like 3^(n/2), so it must be reduced modulo 10^9 + 7 as you go; it never fits in a 64-bit integer otherwise.
n reaches 99999, so the two input lines together reach 200000 bytes. Read them with buffered input and use a single left-to-right pass.
Letters repeat once n > 52; never try to identify a domino by looking up "the other cell with the same letter". Use the column rules.