分数: 400 点
问题陈述
我们有一个带有 2 \times N 网格。 Snuke 覆盖了棋盘 N 没有重叠的多米诺骨牌。 在这里,多米诺骨牌可以覆盖 1 \times 2 or 2 \times 1 广场。
然后,Snuke 决定使用三种颜色来绘制这些多米诺骨牌:红色、青色和绿色。 相邻的两个多米诺骨牌应该涂上不同的颜色。 在这里,并不总是需要使用所有三种颜色。
求这种绘制多米诺骨牌的方法的数量,取模 1000000007.
多米诺骨牌的排列方式以两根绳子的形式提供给您 S_1 和 S_2 按以下方式:
- 每张多米诺骨牌都由不同的英文字母(小写或大写)表示。
- 的 j- 第一个字符 S_i 代表占据正方形的多米诺骨牌 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