← 返回题目列表

AtCoder · arc081_b

D. 着色多米诺骨牌

中文机器翻译题面 查看原题

分数: 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