[ABC071D] Coloring Dominoes
题意翻译
Snuke有一个$2\times N$的矩阵,以及$N$个多米诺骨牌,每一个骨牌是$1\times 2$或者$2 \times 1$的
现在Snuke决定用红色、浅蓝色和绿色三种颜色来绘制这些骨牌,要保证每一个骨牌与其周围相邻的骨牌颜色都不一样
问一共有多少种不同的方案,答案对$1e9+7$取模
- 每一个骨牌都会用一个英文字母表示
- 保证每一个骨牌的字母都不一样
题目描述
[problemUrl]: https://atcoder.jp/contests/abc071/tasks/arc081_b
$ 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 $ で出力せよ．
输入输出样例
输入样例 #1
3
aab
ccb输出样例 #1
6输入样例 #2
1
Z
Z输出样例 #2
3输入样例 #3
52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn输出样例 #3
958681902说明
### 制約
- $ 1\ \leq\ N\ \leq\ 52 $
- $ |S_1|\ =\ |S_2|\ =\ N $
- $ S_1,\ S_2 $ は英小文字または英大文字からなる
- $ S_1,\ S_2 $ は正しいドミノの敷き詰め方を表している
### Sample Explanation 1
次の $ 6 $ 通りあります． !\[\](https://atcoder.jp/img/arc081/899673bd23529f4fb5e41c6e7d5bc372.png)
### Sample Explanation 2
必ずしもすべての色を使わなくてもよいことに注意してください．