棋盘游戏
题号：NC53236
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2016 Day1 T3 「ソリティア」
JOI君有一个棋盘，棋盘上有N行3列的格子。JOI君有若干棋子，并想用它们来玩一个游戏。初始状态棋盘上至少有一个棋子，也至少有一个空位。
游戏的目标是：在还没有放棋子的格子上依次放棋子，并填满整个棋盘。在某个格子上放置棋子必须满足以下条件之一：
  1. 这个格子的上下一格都放有棋子；
  2. 这个格子的左右一格都放有棋子。
JOI君想知道有多少种从初始状态开始，并达到游戏目标的方案，这个答案可能会非常大。请你帮JOI君算出这个答案，并对取模。

输入描述:

第一行有一个整数N，表示棋盘的大小为纵向3格，横向N格。
接下来的三行均为仅由o和x组成的字符串。这三行中第i行的第j个字符表示棋盘中从上到下第i行，从左到右第j个棋子的状态。其中o表示开始时有棋子被放置，x表示开始时这个位置为没有放置着棋子。

输出描述:

一个整数，表示符合条件的方案个数。
示例1

输入

复制 
3
oxo
xxo
oxo

输出

复制 
14

说明

对于样例1，游戏的初始状态如下图所示（用◯表示有棋子放置）：
以下是所有可以从初始状态达到最终状态的方案（序号为放棋子的顺序）：

一共有14种方案，因此输出14。
示例2

输入

复制 
10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

输出

复制 
149022720
示例3

输入

复制 
10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

输出

复制 
0

说明

没有可以达到最终状态的方案。
示例4

输入

复制 
20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

输出

复制 
228518545

备注:

对于所有数据，满足。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2731