解法
縦になっているドミノ1本と、横になっているドミノ2本をそれぞれ1セットとして考えていきます。これは、文字目の上下が一致しているかどうかを調べるだけで簡単に判断できます。横になっているセットについては、次のセットに行くときに、
番目の文字ではなく
番目の文字を見るようにしておきます。
この問題では、左から順番に見ていくと、セット目のドミノについて、
セット目のドミノ以外は色の付け方に影響がありません。
番目より手前のドミノは
番目の色の付け方とは無関係です。
ので、左から順番に見ていくだけで答えを求めることができます。
まず、一番左のセットについての塗り方を考えると、
縦のセット:3通り
横のセット:6通り
となります。
次に、セット目のドミノの色の付け方を考えます。
と
番目がどのセットになっているかによるので、4通り存在します。
番目が縦、
番目も縦:
というようにして、番目までの色の付け方を1~3倍していくことで、最終的に最後のドミノまでの色の付け方を求めることができます。
あとは、modをとり忘れないようにしつつ、計算していけば答えを求めることができます。
