样例文件

题目描述

有一个箱子，我们将其看作一个 $3$ 行 $N$ 列的网格图。

初始时，小明在网格图中的一些格子中装入了小球，并且留了一些空格子。

你的任务是：在空格子中逐个装入小球，直到网格图中所有格子都被装入小球为止。

显然，你的任务没有这么简单。你向空格子里装球是有规则的。

一个空格子中允许装入小球需满足以下两个条件之一：

（1）该格子上下相邻的两个格子中均已装入了小球。

（2）该格子左右相邻的两个格子中均已装入了小球。

你想知道，完成任务有多少种装入方案？

输出答案 $mod$ $(10^9+7)$.

输入格式

第一行：一个整数 $N$。

接下来是一个 $3$ 行 $N$ 列的 01 字符矩阵 $S$ 表示小明装完球后的状态。若 $S_{i,j} （1 ≤ i ≤ 3, 1 ≤ j ≤ N）$ 为 0 表示第 $i$ 行第 $j$ 列的格子中未装入小球，若为 1 则表示第 $i$ 行第 $j$ 列的格子中已经装入了小球。数据保证字符矩阵中至少包含一个 0，至少包含一个 1。

输出格式

一个整数，表示答案 $mod$ $(10^9+7)$.

样例1输入

3
101
001
101

样例1输出

14

样例 1 解释

网格图初始状态如下所示（用 ◯ 表示已经装入了小球）：

以下是所有的装入方案，其中的数字为装入小球的次序，共有 $14$ 种方案：

样例2输入

3
111
111
110

样例2输出

0

样例2解释

该样例只有右下角一个空格子，但该格子不满足两个装球条件的任何一个，无法装入小球。

样例3输入

20
10110101101011010101
10001010001100000110
10110101101101101011

样例3输出

228518545

数据范围