题目描述

我们有一个 $2 \times N$ 的棋盘。Snuke 用 $N$ 个多米诺骨牌将棋盘覆盖，保证没有重叠。这里，一个多米诺骨牌可以覆盖一个 $1 \times 2$ 或 $2 \times 1$ 的方格。

然后，Snuke 决定使用三种颜色（红色、青色和绿色）来为这些多米诺骨牌上色。相邻的两个多米诺骨牌之间应该使用不同的颜色进行上色。注意，并不一定需要使用全部三种颜色。

计算出多米诺骨牌上色的方法数，答案需要对 $1000000007$ 取模。

多米诺骨牌的排列方式由两个字符串 $S_1$ 和 $S_2$ 给出：

• 每个多米诺骨牌由不同的英文字母表示（小写或大写）。
• $S_i$ 的第 $j$ 个字符表示在从上到下的第 $i$ 行、从左到右的第 $j$ 列处占据方格的多米诺骨牌。

约束条件

• $1 \leq N \leq 52$
• $|S_1| = |S_2| = N$
• $S_1$ 和 $S_2$ 由小写和大写英文字母组成。
• $S_1$ 和 $S_2$ 表示一个有效的多米诺骨牌排列。

输入格式

输入以以下格式从标准输入给出：

$N$ $S_1$ $S_2$

输出格式

打印多米诺骨牌上色的方法数，答案对 $1000000007$ 取模。

示例输入1

3
aab
ccb

示例输出1

6

有六种上色方式，如下所示：

示例输入2

1
Z
Z

示例输出2

3

注意，并不一定需要使用全部三种颜色。

示例输入3

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

示例输出3

958681902