Problem: letitflow (2018 round1)

You've been hired for a boring plumbing installation job. You'll be installing
pipes into a house which can be modeled as a grid with 3 rows and **N**
columns. The _j_th cell in the _i_th row of the grid is described by the
character **Gi,j**, and is either empty (if **Gi,j** = `.`) or is blocked by a
wall (if **Gi,j** = `#`). There's already a pipe incoming into the left edge
of the top-left cell, and another pipe leaving from the right edge of the
bottom-right cell. For example, the house might initially look as follows:

![]({{PHOTO_ID:761755607898954}})

Your job is to install one or more additional pipes in empty cells throughout
the house, such that water can successfully flow through them from the top-
left pipe all the way to the bottom-right one. You have access to a whole lot
of pipes, but unfortunately they're all of a single type — elbow-shaped. When
you install such a pipe in a cell, it allows water to flow in from one edge of
the cell, make a 90-degree turn either clockwise or counter-clockwise, and
flow out from another edge of the cell. Each pipe may be installed in any of
the following four rotations:

![]({{PHOTO_ID:603209650305327}})

Pipes may only be installed into empty cells, and no cell may contain multiple
pipes. So as to not waste equipment, each pipe installed must end up actually
contributing to the flow of water -- in other words, you may not install a
pipe if it could be removed without disrupting the flow of water from the top-
left pipe to the bottom-right one. For example, the following diagram
illustrates the only valid set of pipes which could be installed into the
house shown above:

![]({{PHOTO_ID:273247077253892}})

To make the job less boring, you're interested in counting the number of
different valid sets of pipes which you might choose to install. As this
number may be large, you only want to compute its value modulo 1,000,000,007.
Two sets of pipes are considered to be different if one of them includes a
pipe in a cell which is left empty in the other, or if at least one pipe is
installed in a different rotation between them.

### Input

Input begins with an integer **T**, the number of houses. For each house,
there is first a line containing the integer **N**. Then, 3 lines follow, each
containing a string of length **N** containing only the characters `.` and
`#`. The _j_th character of the _i_th line is **Gi,j**.

### Output

For the _i_th house, print a line containing "Case #_i_: " followed by the
number of different valid sets of pipes which could be installed in the _i_th
house (modulo 1,000,000,007).

### Constraints

1 ≤ **T** ≤ 100  
1 ≤ **N** ≤ 1,000  

### Explanation of Sample

In the first case, pipes can be installed only as follows:

![]({{PHOTO_ID:2796578177295687}})

The third case is explained in the problem statement above.



Sample input:
7
2
..
..
..
2
#.
..
.#
4
...#
....
.#..
4
..##
....
.#..
5
.#...
.....
.....
8
....#...
........
#.......
70
......................................................................
......................................................................
......................................................................


Sample output:
Case #1: 1
Case #2: 0
Case #3: 1
Case #4: 0
Case #5: 0
Case #6: 4
Case #7: 179869065



Code: // Let It Flow
// Solution by Jacob Plachta

#define DEBUG 0

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <complex>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <sstream>
using namespace std;

#define LL long long
#define LD long double
#define PR pair<int,int>

#define Fox(i,n) for (i=0; i<n; i++)
#define Fox1(i,n) for (i=1; i<=n; i++)
#define FoxI(i,a,b) for (i=a; i<=b; i++)
#define FoxR(i,n) for (i=(n)-1; i>=0; i--)
#define FoxR1(i,n) for (i=n; i>0; i--)
#define FoxRI(i,a,b) for (i=b; i>=a; i--)
#define Foxen(i,s) for (i=s.begin(); i!=s.end(); i++)
#define Min(a,b) a=min(a,b)
#define Max(a,b) a=max(a,b)
#define Sz(s) int((s).size())
#define All(s) (s).begin(),(s).end()
#define Fill(s,v) memset(s,v,sizeof(s))
#define pb push_back
#define mp make_pair
#define x first
#define y second

template<typename T> T Abs(T x) { return(x<0 ? -x : x); }
template<typename T> T Sqr(T x) { return(x*x); }
string plural(string s) { return(Sz(s) && s[Sz(s)-1]=='x' ? s+"en" : s+"s"); }

const int INF = (int)1e9;
const LD EPS = 1e-12;
const LD PI = acos(-1.0);

#if DEBUG
#define GETCHAR getchar
#else
#define GETCHAR getchar_unlocked
#endif

bool Read(int &x)
{
	char c,r=0,n=0;
	x=0;
		for(;;)
		{
			c=GETCHAR();
				if ((c<0) && (!r))
					return(0);
				if ((c=='-') && (!r))
					n=1;
				else
				if ((c>='0') && (c<='9'))
					x=x*10+c-'0',r=1;
				else
				if (r)
					break;
		}
		if (n)
			x=-x;
	return(1);
}

#define MOD 1000000007

int N;
char G[3][1001];

int Solve()
{
	int i,j,c,ans;
	// impossible?
		if (N%2)
			return(0);
		if ((G[0][0]=='#') || (G[2][N-1]=='#'))
			return(0);
		Fox(i,N)
			if (G[1][i]=='#')
				return(0);
	// count
	ans=1;
		for (i=1; i<N-1; i+=2)
		{
			c=0;
				for (j=0; j<=2; j+=2)
					if ((G[j][i]!='#') && (G[j][i+1]!='#'))
						c++;
			ans=ans*c%MOD;
		}
	return(ans);
}

int main()
{
		if (DEBUG)
			freopen("in.txt","r",stdin);
	// vars
	int T,t;
	int i;
	// testcase loop
	Read(T);
		Fox1(t,T)
		{
			// input
			Read(N);
				Fox(i,3)
					scanf("%s",&G[i]);
			// output
			printf("Case #%d: %d\n",t,Solve());
		}
	return(0);
}