#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

const int maxn = 12;
const int maxst = 50000 + 5;

const int orz = 19260817;

struct Hash
{
    int cnt[orz];
    ull val[orz];
    int head[orz], nxt[orz], sz;

    void inline insert(ull u, int c)
    {
        int v = u % orz, i, lst = 0;
        for(i = head[v]; i; lst = i, i = nxt[i]) if(val[i] == u) break;
        if(i) cnt[i] = c;
        else {
            if(lst) nxt[lst] = ++sz;
            else head[v] = ++sz;
            val[sz] = u, cnt[sz] = c;
        }
    }

    int inline find(ull u)
    {
        int v = u % orz, i;
        for(i = head[v]; i; i = nxt[i]) if(val[i] == u) return cnt[i];
        return 0;
    }
} vti;
ull itv[maxst]; int tot;

int n, m;
char board[maxn + 3][maxn + 3];
int ptn[maxst][maxn + 2];
int fi, fj;

void inline getptn(int id)
{
    ull st = itv[id];
    int stk[maxn], cnt = 0;
    for(int i = 1; st; st >>= 2, ++i) {
        int p = st & 3;
        if(p == 1) stk[++cnt] = i;
        else  if(p == 2) ptn[id][i] = stk[cnt], ptn[id][stk[cnt--]] = i;
    }
}

void dfs(ull st, int dep, int k)
{
    if(dep > n + 1) {
        if(k) return;
        itv[++tot] = st;
        vti.insert(st, tot);
        return;
    }
    if(k > n + 1 - dep + 1) return;
    dfs(st, dep + 1, k); // #
    dfs(st | (1 << (2 * (dep - 1))), dep + 1, k + 1); // (
    if(k) dfs(st | (2 << (2 * (dep - 1))), dep + 1, k - 1); // )
}

void inline Init()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%s", board[i] + 1);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(board[i][j] == '*') board[i][j] = 0;
            else board[i][j] = 1;
    dfs(0, 1, 0);
    for(int i = 1; i <= tot; ++i) getptn(i);
//    printf("tot = %d\n", tot);
    for(int i = n; i; --i) {
        for(int j = m; j; --j) {
            if(board[i][j]) {
                fi = i, fj = j;
//                printf("fi = %d, fj = %d\n", fi, fj);
                return;
            }
        }
    }
}

ll f[maxn + 2][maxn + 2][maxst];

ull inline fillas(ull S, int k, int c) {
    S &= ~(3 << (2 * (k - 1)));    // set zero
    S |= c << (2 * (k - 1));    // set c
    return S;
}

void inline Solve()
{
    f[0][m][vti.find(0)] = 1;
    for(int i = 0; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            for(int k = 1; k <= tot; ++k) {
                ull st = itv[k];
                if(!f[i][j][k]) continue;    // cut (=^o^=)
//                printf("f[%d][%d][%d] = %lld\n", i, j, k, f[i][j][k]);
                int tj = j + 1, ti = i; if(tj > m) tj = 1, ti = i + 1; // get target.

                int left = (st >> (2 * (tj - 1))) & 3;    // left plug
                int top = (st >> (2 * tj)) & 3;            // top plug
//                printf("[%d, %d] -> [%d, %d] with left = %d, top = %d.\n", i, j, ti, tj, left, top);

                if(!left && !top) {    // no plug
                    if(!board[ti][tj]) {    // if cannot
                        ull S = st;    // do nothing
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    } else if(board[ti + 1][tj] && board[ti][tj + 1]) {    // can ?
                        ull S = fillas(fillas(st, tj, 1), tj + 1, 2); // fill it
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }

                else if(left == 1 && top == 1) { // double left
                    int pp = ptn[k][tj + 1]; // get partner
                    ull S = fillas(fillas(fillas(st, tj, 0), tj + 1, 0), pp, 1);
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 2 && top == 2) {    // double right
                    int pp = ptn[k][tj];    // get partner
                    ull S = fillas(fillas(fillas(st, tj, 0), tj + 1, 0), pp, 2);
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 2 && top == 1) {    // right and left
                    ull S = fillas(fillas(st, tj, 0), tj + 1, 0);    // connect them directly
                    if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                    f[ti][tj][vti.find(S)] += f[i][j][k];
                }

                else if(left == 1 && top == 2) {    // left and right
                    if(ti == fi && tj == fj) {    // end block only
                        ull S = fillas(fillas(st, tj, 0), tj + 1, 0);    // connect them directly
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }

                else {    // one have plug but another no
//                    printf("ah?\n");
                    if(board[ti + 1][tj]) {    // if down can to
                        ull S = fillas(fillas(st, tj, left + top), tj + 1, 0);    // set
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
//                        printf("%d %llu\n", vti.find(S), S);
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                    if(board[ti][tj + 1]) {    // if right canto
                        ull S = fillas(fillas(st, tj, 0), tj + 1, left + top);    // set
                        if(tj == m) S = fillas(S, n + 1, 0), S <<= 2;
                        f[ti][tj][vti.find(S)] += f[i][j][k];
                    }
                }
            }
        }
    }
}

int main()
{
    Init();
/*    for(int i = 1; i <= tot; ++i) {
        printf("id: %d, st: %llu\n", i, itv[i]);
    }*/
    Solve();
    printf("%lld\n", f[n][m][1]);
    return 0;
}

Don't want to read the code, but 39 test apparently is something like less than 12 rows with 12 columns and all empty. I had bug in this one:

2 12
............
............

Result should be obviously 1.