AT_arc081_b [ABC071D] Coloring Dominoes

有一个 $2 \times N$ 的格子。すぬけ君在这个格子上铺设了 $N$ 个多米诺骨牌，保证不会有重叠。这里，多米诺骨牌可以覆盖 $1 \times 2$ 或 $2 \times 1$ 的格子。 すぬけ君打算用红色、水色和绿色三种颜色来给这些多米诺骨牌上色。此时，边上相接的多米诺骨牌必须涂成不同的颜色。不需要一定使用全部三种颜色。 请问，满足条件的多米诺骨牌上色方案共有多少种？请将答案对 $1000000007$ 取模后输出。 多米诺骨牌的铺设方式由字符串 $S_1, S_2$ 以如下方式给出： - 每个多米诺骨牌由不同的小写或大写英文字母表示。 - $S_i$ 的第 $j$ 个字符表示从上到下第 $i$ 行、从左到右第 $j$ 列格子覆盖的多米诺骨牌是哪一个。

输入以以下格式从标准输入给出。 > $N$ > $S_1$ > $S_2$

输出多米诺骨牌的上色方案数，对 $1000000007$ 取模。

## 限制条件 - $1 \leq N \leq 52$ - $|S_1| = |S_2| = N$ - $S_1, S_2$ 由大小写英文字母组成 - $S_1, S_2$ 表示正确的多米诺骨牌铺设方式 ## 样例解释 1 共有如下 $6$ 种方案。  ## 样例解释 2 请注意，不一定需要使用全部颜色。 由 ChatGPT 5 翻译