FbHkrCup 18-R1-A

#define ll long long
#include <bits/stdc++.h>
using namespace std;

const int OO = 1e9;
const double EPS = 1e-9;
const ll MOD =1e9 + 7;

ll mem[3][1000][2];
char graph[3][1000];
ll n;
ll solve(int r, int c, int d) {
    if(r == 2 && c == n && d == 0) {
        return 1;
    }
    if(r < 0 || r > 2 || c < 0 || c > n-1 || graph[r][c] == '#') {
        return 0;
    }
    if(mem[r][c][d] != -1) {
        return mem[r][c][d];
    }
    ll &ret = mem[r][c][d];
    ret = 0;
    if(d == 1) {
        ret = solve(r,c+1,0)%MOD;
    }
    else {
        ret = (solve(r-1,c,1) + solve(r+1,c,1))%MOD;
    }
    return ret;
}

int main()
{
    freopen("let_it_flow_input.txt","r",stdin);
    freopen("out.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    for(int ti = 1; ti <= t; ti++) {
        cin >> n;
        for(int i = 0; i < 3; i++) {
            for(int j = 0; j < n; j++) {
                cin >> graph[i][j];
                for(int d = 0; d < 2; d++) {
                    mem[i][j][d] = -1;
                }
            }
        }
        cout << "Case #" << ti << ": " << solve(0,0,0) << "\n";
    }
    return 0;
}