题目描述

$2\ \times\ N$ のマス目があります． すぬけ君は，このマス目に $N$ 個のドミノを，重ならないように敷き詰めました． ここで，ドミノは，$1\ \times\ 2$ または $2\ \times\ 1$ のマス目を覆うことができます．

すぬけ君は，赤色，水色，緑色の $3$ 色を使って，これらのドミノを塗ることにしました． このとき，辺で接しているドミノは異なる色で塗るようにします． ここで，必ずしも $3$ 色すべてを使う必要はありません．

このような塗り方が何通りあるかを mod $1000000007$ で求めてください．

ただし，ドミノの敷き詰め方は，文字列 $S_1,\ S_2$ を用いて，次のようにして与えられます．

• 各ドミノは，それぞれ異なる英小文字または英大文字で表される．
• $S_i$ の $j$ 文字目は，マス目の上から $i$ 番目，左から $j$ 番目のマスにどのドミノがあるかを表す．

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S_1$ $S_2$

输出格式

ドミノを塗る方法の数を mod $1000000007$ で出力せよ．

题目大意

Snuke有一个$2\times N$的矩阵,以及$N$个多米诺骨牌,每一个骨牌是$1\times 2$或者$2 \times 1$的
现在Snuke决定用红色、浅蓝色和绿色三种颜色来绘制这些骨牌,要保证每一个骨牌与其周围相邻的骨牌颜色都不一样
问一共有多少种不同的方案,答案对$1e9+7$取模

• 每一个骨牌都会用一个英文字母表示
• 保证每一个骨牌的字母都不一样

3
aab
ccb

6

1
Z
Z

3

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

958681902

提示

制約

• $1\ \leq\ N\ \leq\ 52$
• $|S_1|\ =\ |S_2|\ =\ N$
• $S_1,\ S_2$ は英小文字または英大文字からなる
• $S_1,\ S_2$ は正しいドミノの敷き詰め方を表している

Sample Explanation 1

次の $6$ 通りあります． 

Sample Explanation 2

必ずしもすべての色を使わなくてもよいことに注意してください．