Queens on Board

You have an N * M chessboard on which some squares are blocked out. In how many ways can you place one or more queens on the board, such that, no two queens attack each other? Two queens attack each other, if one can reach the other by moving horizontally, vertically, or diagonally without passing over any blocked square. At most one queen can be placed on a square. A queen cannot be placed on a blocked square.

Input Format

The first line contains the number of test cases T. T test cases follow. Each test case contains integers N and M on the first line. The following N lines contain M characters each, and represent a board. A '#' represents a blocked square and a '.' represents an unblocked square.

Constraints

1 <= T <= 100 

1 <= N <= 50 

1 <= M <= 5

Output Format

Output T lines containing the required answer for each test case. As the answers can be really large, output them modulo 10^{9}+7.

Sample Input
4  
3 3  
...  
...  
...  
3 3  
.#.  
.#.  
...  
2 4  
.#..  
....  
1 1  
#

Sample Output
17  
18  
14  
0

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Dynamic programming


Solutions:
def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
mod = 1000000007
for case in range(int(input())):
	(Y, X) = map(int, input().split())
	mx = [int(''.join(('0' if c == '.' else '1' for c in input().rstrip())), 2) for i in range(Y)]
	full = (1 << X) - 1

	def is_wall(x, y):
		return mx[y] & 1 << x != 0 if 0 <= x < X and 0 <= y < Y else True

	def get_free(mx):
		y = 0
		while y < Y and mx[y] == full:
			y += 1
		if y == Y:
			return (None, None)
		free = 0
		while mx[y] & 1 << free != 0:
			free += 1
		if free >= X:
			return (None, None)
		return (free, y)

	def place_queen(x, y, mx):
		nmx = list(mx)
		for dx in [-1, 0, 1]:
			for dy in [-1, 0, 1]:
				if dx == 0 and dy == 0:
					continue
				(cx, cy) = (x, y)
				while not is_wall(cx, cy):
					nmx[cy] |= 1 << cx
					(cx, cy) = (cx + dx, cy + dy)
		return tuple(nmx)

	@memoize
	def rec(mx):
		(free_x, free_y) = get_free(mx)
		if free_x == None:
			return 0
		imx = list(mx)
		imx[free_y] |= 1 << free_x
		ans = rec(tuple(imx))
		nmx = place_queen(free_x, free_y, mx)
		ans += 1
		(free_x, free_y) = get_free(nmx)
		if free_x != None:
			ans += rec(nmx)
		return ans % mod
	print(rec(tuple(mx)))


mod = 10 ** 9 + 7
positions = dict()

def get_positions(board_raw, m):
	if board_raw not in positions:
		positions[board_raw] = []
		for i in range((1 << m) - 1, -1, -1):
			j = m
			can_place_queen = True
			configuration_valid = True
			while j > 0:
				if board_raw & 1 << j - 1 != 0:
					can_place_queen = True
				if i & 1 << j - 1 != 0:
					if board_raw & 1 << j - 1 == 0 and can_place_queen == True:
						can_place_queen = False
					else:
						configuration_valid = False
						break
				j = j - 1
			if configuration_valid == True:
				positions[board_raw].append(i)
	return positions[board_raw]

def print_dp(dp):
	print('Final:')
	for (key, value) in dp.items():
		print('{0:b}'.format(key), ':')
		for (key2, value2) in value.items():
			print('\t\t', '{0:b}'.format(key2), ':', value2)
t = int(input())
while t:
	positions = dict()
	str = input().split()
	n = int(str[0])
	m = int(str[1])
	b = [[0] * m for i in range(n)]
	board = [0] * (n + 1)
	for i in range(n):
		str = input()
		for j in range(m):
			if str[j] == '#':
				b[i][j] = 1
				board[i] |= 1 << m - j - 1
	dp = dict()
	for i in range((1 << m) - 1, -1, -1):
		j = m
		can_place_queen = True
		configuration_valid = True
		left_diagonal_attack = 0
		straight_attack = 0
		right_diagonal_attack = 0
		while j >= 0:
			if b[0][m - j - 1] == 1:
				can_place_queen = True
			if i & 1 << j != 0:
				if b[0][m - j - 1] == 0 and can_place_queen == True:
					can_place_queen = False
				else:
					configuration_valid = False
					break
			j = j - 1
		if configuration_valid == True:
			l_d_a = i << 1 & 2 ** m - 1 & ~board[1]
			m_a = i & ~board[1]
			r_d_a = i >> 1 & ~board[1]
			next_attack = l_d_a << 2 * m | m_a << m | r_d_a
			next_pos = i << 1 & 2 ** m - 1 | i | i >> 1
			if next_pos not in dp:
				dp[next_pos] = dict()
			if next_attack not in dp[next_pos]:
				dp[next_pos][next_attack] = 0
			dp[next_pos][next_attack] += 1
	for i in range(1, n, 1):
		pos = get_positions(board[i], m)
		dp2 = dict()
		for (key, value) in dp.items():
			for p in pos:
				if ~key & p == p:
					for (key2, value2) in value.items():
						next_pos = p << 1 & 2 ** m - 1 | p | p >> 1
						current_attack = key2
						l_d_a = current_attack >> 2 * m
						m_a = current_attack >> m & 2 ** m - 1
						r_d_a = current_attack & 2 ** m - 1
						l_d_a = (l_d_a << 1 | p << 1) & 2 ** m - 1 & ~board[i + 1]
						m_a = (m_a | p) & 2 ** m - 1 & ~board[i + 1]
						r_d_a = (r_d_a >> 1 | p >> 1) & 2 ** m - 1 & ~board[i + 1]
						next_attack = l_d_a << 2 * m | m_a << m | r_d_a
						next_pos = next_pos | l_d_a | m_a | r_d_a
						if next_pos not in dp2:
							dp2[next_pos] = dict()
						if next_attack not in dp2[next_pos]:
							dp2[next_pos][next_attack] = 0
						dp2[next_pos][next_attack] += value2
		dp = dp2
	res = 0
	for (key, value) in dp.items():
		for (key2, value2) in value.items():
			res += value2
	print((res - 1) % mod)
	t -= 1


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
mod = 1000000007
for case in range(int(input())):
	(Y, X) = map(int, input().split())
	mx = [int(''.join(('0' if c == '.' else '1' for c in input().rstrip())), 2) for i in range(Y)]
	full = (1 << X) - 1

	def is_wall(x, y):
		return mx[y] & 1 << x != 0 if 0 <= x < X and 0 <= y < Y else True

	def get_free(mx):
		y = 0
		while y < Y and mx[y] == full:
			y += 1
		if y == Y:
			return (None, None)
		free = 0
		while mx[y] & 1 << free != 0:
			free += 1
		if free >= X:
			return (None, None)
		return (free, y)

	def place_queen(x, y, mx):
		nmx = list(mx)
		for dx in [-1, 0, 1]:
			for dy in [-1, 0, 1]:
				if dx == 0 and dy == 0:
					continue
				(cx, cy) = (x, y)
				while not is_wall(cx, cy):
					nmx[cy] |= 1 << cx
					(cx, cy) = (cx + dx, cy + dy)
		return tuple(nmx)

	@memoize
	def rec(mx):
		(free_x, free_y) = get_free(mx)
		if free_x == None:
			return 0
		imx = list(mx)
		imx[free_y] |= 1 << free_x
		ans = rec(tuple(imx))
		nmx = place_queen(free_x, free_y, mx)
		ans += 1
		(free_x, free_y) = get_free(nmx)
		if free_x != None:
			ans += rec(nmx)
		return ans % mod
	print(rec(tuple(mx)))


def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
mod = 1000000007
for case in range(int(input())):
	(Y, X) = map(int, input().split())
	mx = [int(''.join(('0' if c == '.' else '1' for c in input().rstrip())), 2) for i in range(Y)]
	full = (1 << X) - 1

	def is_wall(x, y):
		return mx[y] & 1 << x != 0 if 0 <= x < X and 0 <= y < Y else True

	def get_free(mx):
		y = 0
		while y < Y and mx[y] == full:
			y += 1
		if y == Y:
			return (None, None)
		free = 0
		while mx[y] & 1 << free != 0:
			free += 1
		if free >= X:
			return (None, None)
		return (free, y)

	def place_queen(x, y, mx):
		nmx = list(mx)
		for dx in [-1, 0, 1]:
			for dy in [-1, 0, 1]:
				if dx == 0 and dy == 0:
					continue
				(cx, cy) = (x, y)
				while not is_wall(cx, cy):
					nmx[cy] |= 1 << cx
					(cx, cy) = (cx + dx, cy + dy)
		return tuple(nmx)

	@memoize
	def rec(mx):
		(free_x, free_y) = get_free(mx)
		if free_x == None:
			return 0
		imx = list(mx)
		imx[free_y] |= 1 << free_x
		ans = rec(tuple(imx))
		nmx = place_queen(free_x, free_y, mx)
		ans += 1
		(free_x, free_y) = get_free(nmx)
		if free_x != None:
			ans += rec(nmx)
		return ans % mod
	print(rec(tuple(mx)))


import collections
QUEEN = 'q'
BLOCK = '#'
SigBlock = collections.namedtuple('SigBlock', 'left middle right')
ROW_QUEENS = {'.....': [[], [0], [1], [2], [3], [4]], '#....': [[], [1], [2], [3], [4]], '.#...': [[], [0], [2], [3], [4], [0, 2], [0, 3], [0, 4]], '..#..': [[], [0], [1], [3], [4], [0, 3], [0, 4], [1, 3], [1, 4]], '...#.': [[], [0], [1], [2], [4], [0, 4], [1, 4], [2, 4]], '....#': [[], [0], [1], [2], [3]], '##...': [[], [2], [3], [4]], '#.#..': [[], [1], [3], [4], [1, 3], [1, 4]], '#..#.': [[], [1], [2], [4], [1, 4], [2, 4]], '#...#': [[], [1], [2], [3]], '.##..': [[], [0], [3], [4], [0, 3], [0, 4]], '.#.#.': [[], [0], [2], [4], [0, 2], [0, 4], [2, 4], [0, 2, 4]], '.#..#': [[], [0], [2], [3], [0, 2], [0, 3]], '..##.': [[], [0], [1], [4], [0, 4], [1, 4]], '..#.#': [[], [0], [1], [3], [0, 3], [1, 3]], '...##': [[], [0], [1], [2]], '###..': [[], [3], [4]], '##.#.': [[], [2], [4], [2, 4]], '##..#': [[], [2], [3]], '#.##.': [[], [1], [4], [1, 4]], '#.#.#': [[], [1], [3], [1, 3]], '#..##': [[], [1], [2]], '.###.': [[], [0], [4], [0, 4]], '.##.#': [[], [0], [3], [0, 3]], '.#.##': [[], [0], [2], [0, 2]], '..###': [[], [0], [1]], '####.': [[], [4]], '###.#': [[], [3]], '##.##': [[], [2]], '#.###': [[], [1]], '.####': [[], [0]], '#####': [[]], '....': [[], [0], [1], [2], [3]], '#...': [[], [1], [2], [3]], '.#..': [[], [0], [2], [3], [0, 2], [0, 3]], '..#.': [[], [0], [1], [3], [0, 3], [1, 3]], '...#': [[], [0], [1], [2]], '##..': [[], [2], [3]], '#.#.': [[], [1], [3], [1, 3]], '#..#': [[], [1], [2]], '.##.': [[], [0], [3], [0, 3]], '.#.#': [[], [0], [2], [0, 2]], '..##': [[], [0], [1]], '###.': [[], [3]], '##.#': [[], [2]], '#.##': [[], [1]], '.###': [[], [0]], '####': [[]], '...': [[], [0], [1], [2]], '#..': [[], [1], [2]], '.#.': [[], [0], [2], [0, 2]], '..#': [[], [0], [1]], '##.': [[], [2]], '#.#': [[], [1]], '.##': [[], [0]], '###': [[]], '..': [[], [0], [1]], '#.': [[], [1]], '.#': [[], [0]], '##': [[]], '.': [[], [0]], '#': [[]]}

def sig_str(sig):
	return ''.join(('./'[s.left] + '.|'[s.middle] + '.\\'[s.right] for s in sig))

def print_sig_counts(sig_counts):
	for (sig, count) in sig_counts.items():
		print('\t{0}: {1}'.format(sig_str(sig), count))
QUEEN_SIG = SigBlock(1, 1, 1)

def transform(sig, row):
	m = len(sig)

	def new_sig():
		for i in range(m):
			if row[i] == BLOCK:
				yield SigBlock(0, 0, 0)
			else:
				middle = sig[i].middle
				left = sig[i + 1].left if i < m - 1 else 0
				right = sig[i - 1].right if i > 0 else 0
				yield SigBlock(left, middle, right)
	base = list(new_sig())
	for queen_pos in ROW_QUEENS[row]:
		copy = list(base)
		for i in queen_pos:
			if any(base[i]):
				break
			copy[i] = QUEEN_SIG
		else:
			yield tuple(copy)

def base_sig(m):
	return tuple([SigBlock(0, 0, 0)] * m)

def count_ways(m, rows):
	sig_counts = {base_sig(m): 1}
	for row in rows:
		transformed = collections.defaultdict(int)
		for (sig, count) in sig_counts.items():
			for new_sig in transform(sig, row):
				transformed[new_sig] += count
		sig_counts = transformed
	return sum(sig_counts.values()) - 1

def read_input_boards():
	import sys
	stdin = iter(sys.stdin)
	line = lambda : next(stdin).strip()
	t = int(line())
	for _ in range(t):
		(n, m) = [int(i) for i in line().split()]
		rows = [line() for _ in range(n)]
		yield (m, rows)
for (m, rows) in read_input_boards():
	print(count_ways(m, rows) % (10 ** 9 + 7))


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


import math
import os
import random
import re
import sys
from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


import math
import os
import random
import re
import sys
from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	grid = []
	for line in range(N):
		grid.append(input())
	tmp_map = {}
	rs = RowState([(False,) * 3 for _ in range(M)], 1)
	tmp_map[rs] = rs
	for x in range(N):
		nmap = {}
		for state in tmp_map:
			dfs(nmap, state, grid, x, M, 0, [], False)
			tmp_map = nmap
	ans = 0
	for key in tmp_map:
		ans += key.count
	print((ans - 1) % 1000000007)


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


import math
import os
import random
import re
import sys
from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
mod = 1000000007
for case in range(int(input())):
	(Y, X) = map(int, input().split())
	mx = [int(''.join(('0' if c == '.' else '1' for c in input().rstrip())), 2) for i in range(Y)]
	full = (1 << X) - 1

	def is_wall(x, y):
		return mx[y] & 1 << x != 0 if 0 <= x < X and 0 <= y < Y else True

	def get_free(mx):
		y = 0
		while y < Y and mx[y] == full:
			y += 1
		if y == Y:
			return (None, None)
		free = 0
		while mx[y] & 1 << free != 0:
			free += 1
		if free >= X:
			return (None, None)
		return (free, y)

	def place_queen(x, y, mx):
		nmx = list(mx)
		for dx in [-1, 0, 1]:
			for dy in [-1, 0, 1]:
				if dx == 0 and dy == 0:
					continue
				(cx, cy) = (x, y)
				while not is_wall(cx, cy):
					nmx[cy] |= 1 << cx
					(cx, cy) = (cx + dx, cy + dy)
		return tuple(nmx)

	@memoize
	def rec(mx):
		(free_x, free_y) = get_free(mx)
		if free_x == None:
			return 0
		imx = list(mx)
		imx[free_y] |= 1 << free_x
		ans = rec(tuple(imx))
		nmx = place_queen(free_x, free_y, mx)
		ans += 1
		(free_x, free_y) = get_free(nmx)
		if free_x != None:
			ans += rec(nmx)
		return ans % mod
	print(rec(tuple(mx)))


def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
mod = 1000000007
for case in range(int(input())):
	(Y, X) = map(int, input().split())
	mx = [int(''.join(('0' if c == '.' else '1' for c in input().rstrip())), 2) for i in range(Y)]
	full = (1 << X) - 1

	def is_wall(x, y):
		return mx[y] & 1 << x != 0 if 0 <= x < X and 0 <= y < Y else True

	def get_free(mx):
		y = 0
		while y < Y and mx[y] == full:
			y += 1
		if y == Y:
			return (None, None)
		free = 0
		while mx[y] & 1 << free != 0:
			free += 1
		if free >= X:
			return (None, None)
		return (free, y)

	def place_queen(x, y, mx):
		nmx = list(mx)
		for dx in [-1, 0, 1]:
			for dy in [-1, 0, 1]:
				if dx == 0 and dy == 0:
					continue
				(cx, cy) = (x, y)
				while not is_wall(cx, cy):
					nmx[cy] |= 1 << cx
					(cx, cy) = (cx + dx, cy + dy)
		return tuple(nmx)

	@memoize
	def rec(mx):
		(free_x, free_y) = get_free(mx)
		if free_x == None:
			return 0
		imx = list(mx)
		imx[free_y] |= 1 << free_x
		ans = rec(tuple(imx))
		nmx = place_queen(free_x, free_y, mx)
		ans += 1
		(free_x, free_y) = get_free(nmx)
		if free_x != None:
			ans += rec(nmx)
		return ans % mod
	print(rec(tuple(mx)))


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


def memoize(func):
	pool = {}

	def wrapper(*arg):
		if arg not in pool:
			pool[arg] = func(*arg)
		return pool[arg]
	return wrapper
mod = 1000000007
for case in range(int(input())):
	(Y, X) = map(int, input().split())
	mx = [int(''.join(('0' if c == '.' else '1' for c in input().rstrip())), 2) for i in range(Y)]
	full = (1 << X) - 1

	def is_wall(x, y):
		return mx[y] & 1 << x != 0 if 0 <= x < X and 0 <= y < Y else True

	def get_free(mx):
		y = 0
		while y < Y and mx[y] == full:
			y += 1
		if y == Y:
			return (None, None)
		free = 0
		while mx[y] & 1 << free != 0:
			free += 1
		if free >= X:
			return (None, None)
		return (free, y)

	def place_queen(x, y, mx):
		nmx = list(mx)
		for dx in [-1, 0, 1]:
			for dy in [-1, 0, 1]:
				if dx == 0 and dy == 0:
					continue
				(cx, cy) = (x, y)
				while not is_wall(cx, cy):
					nmx[cy] |= 1 << cx
					(cx, cy) = (cx + dx, cy + dy)
		return tuple(nmx)

	@memoize
	def rec(mx):
		(free_x, free_y) = get_free(mx)
		if free_x == None:
			return 0
		imx = list(mx)
		imx[free_y] |= 1 << free_x
		ans = rec(tuple(imx))
		nmx = place_queen(free_x, free_y, mx)
		ans += 1
		(free_x, free_y) = get_free(nmx)
		if free_x != None:
			ans += rec(nmx)
		return ans % mod
	print(rec(tuple(mx)))


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


import math
import os
import random
import re
import sys
from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()


from operator import __add__
from functools import reduce

class RowState(object):

	def __init__(self, rows, count):
		self.rows = rows
		self.count = count

	def __hash__(self):
		return hash(tuple(reduce(__add__, self.rows)))

	def __eq__(self, that):
		return self.rows == that.rows

def dfs(nmap, rowState, grid, x, M, depth, cur, h):
	if depth == M:
		testState = RowState(cur[:], rowState.count)
		if testState in nmap:
			nmap[testState].count += rowState.count
		else:
			nmap[testState] = testState
	elif grid[x][depth] == '#':
		cur.append((False,) * 3)
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
		cur.pop()
	else:
		(v, d, r) = (False, False, False)
		if rowState.rows[depth][0]:
			v = True
		if depth > 0 and rowState.rows[depth - 1][1]:
			d = True
		if depth < M - 1 and rowState.rows[depth + 1][2]:
			r = True
		if not v and (not d) and (not r) and (not h):
			cur.append((True,) * 3)
			dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
			cur.pop()
		cur.append((v, d, r))
		dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
		cur.pop()

def main():
	for _ in range(int(input())):
		(N, M) = map(int, input().split())
		grid = []
		for line in range(N):
			grid.append(input())
		tmp_map = {}
		rs = RowState([(False,) * 3 for _ in range(M)], 1)
		tmp_map[rs] = rs
		for x in range(N):
			nmap = {}
			for state in tmp_map:
				dfs(nmap, state, grid, x, M, 0, [], False)
				tmp_map = nmap
		ans = 0
		for key in tmp_map:
			ans += key.count
		print((ans - 1) % 1000000007)
main()