问题描述

我们有一块带有 $2×N$ 个网格的板。光头强用没有重叠的 $N$ 多米诺骨牌覆盖了棋盘。

在这里，多米诺骨牌可以覆盖 $1×2$ 或 $2×1$ 方块。

然后，光头强决定用三种颜色来画这些多米诺骨牌：红色、黄色和蓝色。

相邻的两张骨牌应涂上不同的颜色。在这里，并不总是需要使用所有三种颜色。求用这种方法画多米诺骨牌的次数，模 $1000000007$。

多米诺骨牌的排列方式为两个字符串 $S_1$​ 和 $S_2$​ ，方式如下：

• 每个多米诺骨牌由不同的英文字母(小写或大写)编号。
• $S_i$​ 中的第 $j$ 个字符表示占据第 $i$ 行第 $j$ 列的骨牌编号。

输入格式

共三行，第一行是一个整数 $N(1≤N≤52)$

$∣S_1​∣=∣S_2​∣=N$

$S_1$​ 和 $S_2$​ 由小写和大写英文字母组成。

$S_1$​ 和 $S_2$​ 表示多米诺骨牌的有效排列。

输出格式

输出这些方法的数量来绘制多米诺骨牌，模$1000000007$。

3
aab
ccb

6

有六种涂色方法。请注意方块的位置是由输入确定的。

1
Z
Z

3

请注意，并不总是需要使用所有颜色。

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

958681902