题目描述

有一个 $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

输入

3
aab
ccb

输出

6

样例 2

输入

1
Z
Z

输出

3

样例 3

输入

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

输出

958681902

说明/提示

限制条件

• $1 \leq N \leq 52$
• $|S_1| = |S_2| = N$
• $S_1, S_2$ 由大小写英文字母组成
• $S_1, S_2$ 表示正确的多米诺骨牌铺设方式

样例解释 1

共有如下 $6$ 种方案。

样例解释 2

请注意，不一定需要使用全部颜色。

由 ChatGPT 5 翻译