Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Bearland can be represented as a square grid that consists of N rows and N columns.
Two cells are called adjacent if they share a side.
In the input, each cell is described by one character:

'.' is an empty cell.
'B', 'G' or 'P' is a cell inhabited by bears of one species — brown, grizzly or polar bears respectively.
'?' is a cell inhabited by bears of one species but you don't know which one.
Note that this cell can't be empty.

Grizzly bears are the most aggressive species.
If a cell is inhabited by grizzly bears, all adjacent cells should be empty, because otherwise there would be fights between bears.

Brown and polar bears are a bit calmer.
All brown bears are fine with other brown bears in adjacent cells, but they would fight with bears of any other species.
Similarly, polar bears would fight with bears of any species other than polar bears.

Let X denote the number of question marks.
Since each question mark represents one of the three species, there are 3^{X} ways to replace them with characters 'B', 'G' and 'P' (denoting the species that live in that cell).
Find the number of such ways that there are no fights between bears.
Print the answer modulo (10^{9}+7).

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains an integer N denoting the size of the grid.

The following N lines describe the grid.
Each of those lines contains a string of length N.
Each character is one of five: '.', '?', 'B', 'G', 'P'.

------ Output ------ 

For each test case, output a single line containing one integer — the number of ways to replace question marks to avoid fights in Bearland, modulo (10^{9}+7).

------ Constraints ------ 

$1 ≤ T ≤ 50$
$2 ≤ N ≤ 50$

------ Subtasks ------ 

$Subtask #1 (30 points): 2 ≤ N ≤ 3$
$Subtask #2 (30 points): Each character in the grid will be either '.' or '?'.$
$Subtask #3 (40 points): Original constraints.$

------ Example ------ 

Input:
6
3
..?
.?B
G..
2
GG
..
3
?..
.??
??.
3
??P
???
??B
7
?.?.?.?
.?.?.?.
?.?.?.?
.?.?.?.
?.?.?.?
.?.?.?.
?.?.?.?
2
PP
PP

Output:
1
0
6
0
288603514
1

------ Explanation ------ 

Test case 1. We are given the grid of size 3 × 3. One of the already fixed cells is inhabited by brown bears. They would fight with bears of any species other than brown bears, so adjacent cells with question marks must by inhabited by brown bears as well.
Hence, there is only 1 way to replace question marks (both of them must be replaced by 'B').

Test case 2. In the given grid, there are two adjacent cells both inhabited by grizzly bears.
They will fight with each other, so the answer is 0 — it's impossible to replace question marks so that there would be no fights (it doesn't matter that there are no question marks at all).

Test case 3. There are 6 ways:

B.. B.. G.. G.. P.. P..
.BB .PP .BB .PP .BB .PP
BB. PP. BB. PP. BB. PP.

Test case 4. No matter how we replace question marks, bears in some two adjacent cells will start a fight.
The answer is 0.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal


Solutions:
import sys
sys.setrecursionlimit(5000)

def findConnections(i, j, visited, connections):
	if i > 0:
		if visited[i - 1][j] == False:
			connections[-1].append(land[i - 1][j])
			visited[i - 1][j] = True
			findConnections(i - 1, j, visited, connections)
	if i < N - 1:
		if visited[i + 1][j] == False:
			connections[-1].append(land[i + 1][j])
			visited[i + 1][j] = True
			findConnections(i + 1, j, visited, connections)
	if j > 0:
		if visited[i][j - 1] == False:
			connections[-1].append(land[i][j - 1])
			visited[i][j - 1] = True
			findConnections(i, j - 1, visited, connections)
	if j < N - 1:
		if visited[i][j + 1] == False:
			connections[-1].append(land[i][j + 1])
			visited[i][j + 1] = True
			findConnections(i, j + 1, visited, connections)

def countAns(connections):
	ans = 1
	for i in connections:
		if len(i) == 1 and i == ['?']:
			ans = ans % MOD * 3
		if len(i) > 1:
			if i.count('G') > 0:
				ans = 0
				break
			elif i.count('B') > 0 and i.count('P') > 0:
				ans = 0
				break
			elif i.count('B') > 0 or i.count('P') > 0:
				ans *= 1
			else:
				ans = ans % MOD * 2
	return ans % MOD

def solve(N, land):
	visited = [[True if land[i][j] == '.' else False for j in range(N)] for i in range(N)]
	connections = []
	for i in range(N):
		for j in range(N):
			if visited[i][j] == False:
				visited[i][j] = True
				connections.append([land[i][j]])
				findConnections(i, j, visited, connections)
	ans = countAns(connections)
	return ans
T = int(input())
for case in range(1, T + 1):
	N = int(input())
	land = [[i for i in input()] for j in range(N)]
	MOD = 10 ** 9 + 7
	print(solve(N, land))


import sys

class Cell:

	def __init__(self, group_id, name):
		self.group_id = group_id
		self.name = name

	def getGroupId(self):
		return self.group_id

	def setGroupId(self, group_id):
		self.group_id = group_id

	def getName(self):
		return self.name

def hashfunction(y, x):
	return 100 * y + x

def findCellValue(cells, y, x):
	if hashfunction(y, x) in cells:
		return cells[hashfunction(y, x)]
	return None

def joinGroups(group_id1, group_id2, groups):
	if group_id1 == group_id2:
		return
	if group_id1 < group_id2:
		(group_id1, group_id2) = (group_id2, group_id1)
	group = groups[group_id2]
	for cell in group:
		cell.setGroupId(group_id1)
		groups[group_id1].add(cell)
	del groups[group_id2]

def groupCellsBasedOnAdjacency(grid):
	cells = dict()
	groups = dict()
	new_group_id = 0
	for i in range(len(grid)):
		for j in range(len(grid[i])):
			if grid[i][j] != '.':
				group_id = None
				cellAbove = findCellValue(cells, i - 1, j)
				cellLeft = findCellValue(cells, i, j - 1)
				if cellAbove is not None:
					group_id = cellAbove.getGroupId()
				if cellLeft is not None:
					if group_id is not None:
						joinGroups(cellLeft.getGroupId(), group_id, groups)
					group_id = cellLeft.getGroupId()
				if group_id is None:
					group_id = new_group_id
					groups[group_id] = set()
					new_group_id += 1
				cell = Cell(group_id, grid[i][j])
				groups[group_id].add(cell)
				cells[hashfunction(i, j)] = cell
	return groups

def calculateNumberOfVariations(groups):
	result = 1
	for key in groups.keys():
		numOfUnknown = 0
		numOfPolar = 0
		numOfBrown = 0
		numOfGrizzly = 0
		for cell in groups[key]:
			if cell.getName() == '?':
				numOfUnknown += 1
			elif cell.getName() == 'P':
				numOfPolar += 1
			elif cell.getName() == 'B':
				numOfBrown += 1
			elif cell.getName() == 'G':
				numOfGrizzly += 1
			else:
				raise RuntimeError('Cell ' + cell.getName() + ' should not occur at this stage.')
		if numOfBrown > 0 and numOfPolar > 0 or (numOfBrown + numOfPolar + numOfUnknown + numOfGrizzly > 1 and numOfGrizzly > 0):
			print(0)
			return
		if numOfUnknown + numOfPolar + numOfBrown + numOfGrizzly == numOfUnknown:
			if numOfUnknown == 1:
				result *= 3
			else:
				result *= 2
		else:
			result *= 1
	print(result % 1000000007)

def processGrid(grid):
	groups = groupCellsBasedOnAdjacency(grid)
	calculateNumberOfVariations(groups)

def parseInputIntoGrids(input_data):
	grids = []
	input_split = input_data.split('\n')
	i = 0
	T = int(input_split[i])
	i += 1
	for _ in range(T):
		N = int(input_split[i])
		i += 1
		grid = []
		for _ in range(N):
			grid.append(input_split[i])
			i += 1
		grids.append(grid)
	return grids
input_data = sys.stdin.read()
grids = parseInputIntoGrids(input_data)
for grid in grids:
	processGrid(grid)


import sys
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict

def Neigh(i, j, N):
	L = []
	if i + 1 != N:
		L.append([i + 1, j])
	if j + 1 != N:
		L.append([i, j + 1])
	if i != 0:
		L.append([i - 1, j])
	if j != 0:
		L.append([i, j - 1])
	return L

def chngneigh(Arr, i, j, target):
	ll = Neigh(i, j, N)
	next = []
	for x in ll:
		if Arr[x[0]][x[1]] == '?':
			Arr[x[0]][x[1]] = target
			next.append(x)
	for x in next:
		Arr = chngneigh(Arr, x[0], x[1], target)
	return Arr
for _ in range(int(input())):
	N = int(input())
	Mat = []
	for _ in range(N):
		row = list(input())
		Mat.append(row)
	for i in range(N):
		for j in range(N):
			if Mat[i][j] == 'P':
				Mat = chngneigh(Mat, i, j, 'P')
			elif Mat[i][j] == 'B':
				Mat = chngneigh(Mat, i, j, 'B')
	fine = True
	for i in range(N):
		for j in range(N):
			if Mat[i][j] == '.' or Mat[i][j] == '?':
				pass
			elif Mat[i][j] == 'G':
				ll = Neigh(i, j, N)
				for x in ll:
					if Mat[x[0]][x[1]] != '.':
						fine = False
						break
			elif Mat[i][j] == 'P':
				ll = Neigh(i, j, N)
				for x in ll:
					if Mat[x[0]][x[1]] == 'B' or Mat[x[0]][x[1]] == 'G':
						fine = False
						break
			elif Mat[i][j] == 'B':
				ll = Neigh(i, j, N)
				for x in ll:
					if Mat[x[0]][x[1]] == 'P' or Mat[x[0]][x[1]] == 'G':
						fine = False
						break
		if fine == False:
			break
	if fine == False:
		print('0')
		continue
	else:
		solo = 0
		for i in range(N):
			for j in range(N):
				if Mat[i][j] == '?':
					ll = Neigh(i, j, N)
					yup = True
					for x in ll:
						if Mat[x[0]][x[1]] != '.':
							yup = False
					if yup == True:
						solo += 1
						Mat[i][j] = 'D'
		clustor = 0
		for i in range(N):
			for j in range(N):
				if Mat[i][j] == '?':
					Mat = chngneigh(Mat, i, j, 'c')
					clustor += 1
		answer = pow(3, solo, 1000000007) * pow(2, clustor, 1000000007)
		print(answer % 1000000007)


import sys

def search(grid, grid_visited, x, y, counters, gridSize):
	if x not in range(gridSize) or y not in range(gridSize) or grid_visited[x][y] == 'v' or (grid[x][y] == '.'):
		pass
	else:
		grid_visited[x][y] = 'v'
		if grid[x][y] == 'G':
			counters['grizzly'] += 1
		elif grid[x][y] == 'B':
			counters['brown'] += 1
		elif grid[x][y] == 'P':
			counters['polar'] += 1
		counters['area'] += 1
		search(grid, grid_visited, x + 1, y, counters, gridSize)
		search(grid, grid_visited, x, y + 1, counters, gridSize)
		search(grid, grid_visited, x - 1, y, counters, gridSize)
		search(grid, grid_visited, x, y - 1, counters, gridSize)
testCases = int(sys.stdin.readline())
for testCase in range(testCases):
	gridSize = int(sys.stdin.readline())
	grid = [list(sys.stdin.readline().strip()) for gridRow in range(gridSize)]
	possibilities = 1
	grid_visited = [['' for i in range(gridSize)] for j in range(gridSize)]
	isValid = True
	for x in range(gridSize):
		for y in range(gridSize):
			try:
				if grid[x][y] != '.':
					counters = {'grizzly': 0, 'brown': 0, 'polar': 0, 'area': 0}
					search(grid, grid_visited, x, y, counters, gridSize)
					if counters['brown'] * counters['polar'] != 0 or (counters['area'] > 1 and counters['grizzly'] != 0):
						isValid = False
						break
					elif counters['area'] == 1 and counters['grizzly'] + counters['brown'] + counters['polar'] == 0:
						possibilities *= 3
					elif counters['area'] > 1 and counters['brown'] + counters['polar'] == 0:
						possibilities *= 2
			except Exception:
				pass
		if not isValid:
			possibilities = 0
			break
	possibilities = possibilities % (10 ** 9 + 7)
	print(str(possibilities))


def BFS(graph, s, b):
	queue = []
	queue.append(s)
	count = 0
	graph[s][1] = True
	if b[s[0]][s[1]] == 'P':
		start = 1
	elif b[s[0]][s[1]] == 'B':
		start = 2
	elif b[s[0]][s[1]] == 'G':
		if len(graph[s][0]) == 0:
			return 1
		else:
			return 0
	else:
		start = 0
	while len(queue) != 0:
		v = queue.pop(0)
		count += 1
		for i in graph[v][0]:
			if graph[i][1] == False:
				if b[i[0]][i[1]] == 'G' and len(graph[i][0]) == 0:
					return 1
				elif b[i[0]][i[1]] == 'G':
					return 0
				elif b[i[0]][i[1]] == 'P':
					if start == 0:
						start = 1
					elif start == 1:
						start = 1
					else:
						return 0
				elif b[i[0]][i[1]] == 'B':
					if start == 0:
						start = 2
					elif start == 1:
						return 0
					else:
						start = 2
				graph[i][1] = True
				queue.append(i)
	if start != 0:
		return 1
	elif count == 1:
		return 3
	else:
		return 2
t = int(input())
for k in range(t):
	n = int(input())
	b = []
	for i in range(n):
		c = []
		a = input().rstrip()
		for i in a:
			c.append(i)
		b.append(c)
	graph = dict()
	c = 0
	for i in range(n):
		for j in range(n):
			graph[i, j] = [[], False]
	for i in range(n):
		for j in range(n):
			if b[i][j] != '.':
				k = 0
				while 1 > k and n > i + 1:
					if b[i + 1][j] != '.':
						graph[i, j][0].append((i + 1, j))
					k += 1
				k = 0
				while 1 > k and n > j + 1:
					if b[i][j + 1] != '.':
						graph[i, j][0].append((i, j + 1))
					k += 1
				k = 0
				while 1 > k and i - 1 >= 0:
					if b[i - 1][j] != '.':
						graph[i, j][0].append((i - 1, j))
					k += 1
				k = 0
				while 1 > k and j - 1 >= 0:
					if b[i][j - 1] != '.':
						graph[i, j][0].append((i, j - 1))
					k += 1
				k = 0
			else:
				graph[i, j][1] = True
	y = 1
	for i in range(n):
		for j in range(n):
			if graph[i, j][1] == False:
				x = BFS(graph, (i, j), b)
				y = y * x % 1000000007
	print(y)


from copy import deepcopy
dc = deepcopy

def cnt(a, n):
	ans = 1
	while True:
		change = 0
		for i in range(1, n + 1):
			for j in range(1, n + 1):
				if a[i][j] == 'G':
					if a[i + 1][j] == 'P' or a[i - 1][j] == 'P' or a[i][j - 1] == 'P' or (a[i][j + 1] == 'P') or (a[i + 1][j] == 'B') or (a[i - 1][j] == 'B') or (a[i][j - 1] == 'B') or (a[i][j + 1] == 'B') or (a[i + 1][j] == 'G') or (a[i - 1][j] == 'G') or (a[i][j - 1] == 'G') or (a[i][j + 1] == 'G') or (a[i + 1][j] == '?') or (a[i - 1][j] == '?') or (a[i][j - 1] == '?') or (a[i][j + 1] == '?'):
						ans = 0
				elif a[i][j] == 'B':
					if a[i + 1][j] == 'P' or a[i - 1][j] == 'P' or a[i][j - 1] == 'P' or (a[i][j + 1] == 'P'):
						ans = 0
				elif a[i][j] == '?':
					bcnt = gcnt = pcnt = qcnt = dcnt = 0
					k = a[i + 1][j]
					if k == 'B':
						bcnt += 1
					if k == 'G':
						gcnt += 1
					if k == 'P':
						pcnt += 1
					if k == '?':
						qcnt += 1
					if k == '.':
						dcnt += 1
					k = a[i - 1][j]
					if k == 'B':
						bcnt += 1
					if k == 'G':
						gcnt += 1
					if k == 'P':
						pcnt += 1
					if k == '?':
						qcnt += 1
					if k == '.':
						dcnt += 1
					k = a[i][j - 1]
					if k == 'B':
						bcnt += 1
					if k == 'G':
						gcnt += 1
					if k == 'P':
						pcnt += 1
					if k == '?':
						qcnt += 1
					if k == '.':
						dcnt += 1
					k = a[i][j + 1]
					if k == 'B':
						bcnt += 1
					if k == 'G':
						gcnt += 1
					if k == 'P':
						pcnt += 1
					if k == '?':
						qcnt += 1
					if k == '.':
						dcnt += 1
					if pcnt >= 1 and bcnt >= 1:
						ans = 0
					elif dcnt == 4:
						ans *= 3
						change = 1
						a[i][j] = 'G'
					elif pcnt >= 1:
						a[i][j] = 'P'
						change = 1
					elif bcnt >= 1:
						a[i][j] = 'B'
						change = 1
		if ans == 0:
			return 0
		if change == 0:
			break
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if a[i][j] == '?':
				if a[i + 1][j] != '?' and a[i - 1][j] != '?' and (a[i][j + 1] != '?') and (a[i][j - 1] != '?'):
					a[i][j] = 'B'
					total = cnt(dc(a), n)
					total *= 3
					return ans * total % 1000000007
				total = 0
				a[i][j] = 'G'
				total += cnt(dc(a), n)
				a[i][j] = 'B'
				total += cnt(dc(a), n) * 2
				return ans * total % 1000000007
	return ans % 1000000007

def valid(a, n):
	for i in range(1, n + 1):
		for j in range(1, n + 1):
			if a[i][j] == 'G':
				if a[i + 1][j] == 'P' or a[i - 1][j] == 'P' or a[i][j - 1] == 'P' or (a[i][j + 1] == 'P') or (a[i + 1][j] == 'B') or (a[i - 1][j] == 'B') or (a[i][j - 1] == 'B') or (a[i][j + 1] == 'B') or (a[i + 1][j] == 'G') or (a[i - 1][j] == 'G') or (a[i][j - 1] == 'G') or (a[i][j + 1] == 'G'):
					return False
			elif a[i][j] == 'B':
				if a[i + 1][j] == 'P' or a[i - 1][j] == 'P' or a[i][j - 1] == 'P' or (a[i][j + 1] == 'P'):
					return False
	return True
for _ in range(int(input())):
	n = int(input())
	a = []
	a.append([0] * (n + 2))
	for i in range(1, n + 1):
		a.append(list(input()))
		a[i].insert(0, 0)
		a[i].append(0)
	a.append([0] * (n + 2))
	print(cnt(a, n))


import sys
from functools import reduce
sys.setrecursionlimit(1000000)

class BearAndSpecies:

	def __init__(self, grid):
		self.grid = grid
		self.n = len(grid)
		self.visited = []
		for _ in range(self.n):
			self.visited.append([False] * self.n)
		self.directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		self.numComponents = [1]

	def isValid(self, x, y):
		if (x >= 0 and x < self.n) and (y >= 0 and y < self.n):
			return True
		return False

	def neighboursIsEmpty(self, x, y):
		for (x1, y1) in self.directions:
			dx = x + x1
			dy = y + y1
			if self.isValid(dx, dy) and self.grid[dx][dy] != '.':
				return False
		return True

	def dfs(self, row, col, v):
		for (x, y) in self.directions:
			dx = row + x
			dy = col + y
			if self.isValid(dx, dy) and self.grid[dx][dy] != '.' and (self.visited[dx][dy] == False):
				self.visited[dx][dy] = True
				if self.grid[dx][dy] != '?':
					v.add(self.grid[dx][dy])
				self.dfs(dx, dy, v)
		return v

	def fillBearLand(self):
		for i in range(self.n):
			for j in range(self.n):
				if self.grid[i][j] != '.' and self.visited[i][j] == False:
					self.visited[i][j] = True
					if self.neighboursIsEmpty(i, j):
						self.numComponents.append(3 if self.grid[i][j] == '?' else 1)
					else:
						v = {self.grid[i][j]}
						if self.grid[i][j] == '?':
							v = set()
						result = self.dfs(i, j, v)
						self.numComponents.append(0 if 'G' in result or len(result) == 2 else (2, 1)[len(result) > 0])
		return reduce(lambda x, y: x * y % 1000000007, self.numComponents)
n = int(input())
for _ in range(n):
	m = int(input())
	grid = [input().strip() for _ in range(m)]
	x = BearAndSpecies(grid)
	result = x.fillBearLand()
	print(result)


import sys
from functools import reduce
sys.setrecursionlimit(1000000)
moves = ((0, 1), (0, -1), (1, 0), (-1, 0))

def is_alone(i, j):
	for (di, dj) in moves:
		(ni, nj) = (i + di, j + dj)
		if 0 <= ni < n and 0 <= nj < n and (b[ni][nj] != '.'):
			return False
	return True

def fill(i, j, met):
	for (di, dj) in moves:
		(ni, nj) = (i + di, j + dj)
		if 0 <= ni < n and 0 <= nj < n:
			if b[ni][nj] != '.' and (not v[ni][nj]):
				v[ni][nj] = True
				if b[ni][nj] != '?':
					met.add(b[ni][nj])
				fill(ni, nj, met)
	return met
for _ in range(int(input())):
	n = int(input())
	b = [input().strip() for _ in range(n)]
	v = [[False for _ in range(n)] for _ in range(n)]
	ret = [1]
	for i in range(n):
		for j in range(n):
			if b[i][j] != '.' and (not v[i][j]):
				v[i][j] = True
				if is_alone(i, j):
					ret.append(3 if b[i][j] == '?' else 1)
				else:
					met = fill(i, j, set() if b[i][j] == '?' else set(b[i][j]))
					ret.append(0 if 'G' in met or len(met) == 2 else (2, 1)[len(met) > 0])
	print(reduce(lambda x, y: x * y % 1000000007, ret))


import sys
sys.setrecursionlimit(10000000)

def display(arr):
	for i in arr:
		for j in i:
			print(j, end=' ')
		print('')

def getConnectedComponents(arr):
	components = []
	for i in range(n):
		for j in range(n):
			if visited[i][j]:
				continue
			else:
				comp = []
				queue = [(i, j)]
				visited[i][j] = True
				while len(queue) != 0:
					curr = queue.pop(0)
					comp.append(arr[curr[0]][curr[1]])
					for (a, b) in [(curr[0] - 1, curr[1]), (curr[0] + 1, curr[1]), (curr[0], curr[1] - 1), (curr[0], curr[1] + 1)]:
						if not (a >= 0 and a < n and (b >= 0) and (b < n)) or visited[a][b]:
							continue
						queue.append((a, b))
						visited[a][b] = True
				components.append(comp)
	return components
for t in range(int(input())):
	n = int(input())
	visited = [[False] * n for i in range(n)]
	arr = []
	for i in range(n):
		arr.append(list(input()))
	for i in range(n):
		for j in range(n):
			visited[i][j] = arr[i][j] == '.'
	components = getConnectedComponents(arr)
	ans = 1
	for i in components:
		ques = 0
		p = 0
		b = 0
		g = 0
		for j in i:
			if j == '?':
				ques += 1
			elif j == 'P':
				p += 1
			elif j == 'B':
				b += 1
			elif j == 'G':
				g += 1
		if g and len(i) > 1:
			ans = 0
			break
		elif p and b:
			ans = 0
			break
		elif p == 0 and b == 0 and (g == 0):
			if len(i) == 1:
				ans *= 3
			else:
				ans *= 2
	print(ans % (10 ** 9 + 7))


def getSpecies(arr, n):
	s = []
	nghbr = ('B', 'P')
	count = 1
	for i in range(n):
		for j in range(n):
			if arr[i][j] == '?':
				c = 'N'
				l = 0
				s.append((i, j))
				while len(s) != 0:
					l += 1
					(i1, j1) = s.pop()
					arr[i1][j1] = 'D'
					if i1 != 0:
						if arr[i1 - 1][j1] == '?':
							s.append((i1 - 1, j1))
						if arr[i1 - 1][j1] == 'G':
							return 0
						elif arr[i1 - 1][j1] in nghbr:
							if c == 'N' or c == arr[i1 - 1][j1]:
								c = arr[i1 - 1][j1]
							else:
								return 0
					if j1 != 0:
						if arr[i1][j1 - 1] == '?':
							s.append((i1, j1 - 1))
						elif arr[i1][j1 - 1] == 'G':
							return 0
						elif arr[i1][j1 - 1] in nghbr:
							if c == 'N' or c == arr[i1][j1 - 1]:
								c = arr[i1][j1 - 1]
							else:
								return 0
					if i1 != n - 1:
						if arr[i1 + 1][j1] == '?':
							s.append((i1 + 1, j1))
						elif arr[i1 + 1][j1] == 'G':
							return 0
						elif arr[i1 + 1][j1] in nghbr:
							if c == 'N' or c == arr[i1 + 1][j1]:
								c = arr[i1 + 1][j1]
							else:
								return 0
					if j1 != n - 1:
						if arr[i1][j1 + 1] == '?':
							s.append((i1, j1 + 1))
						elif arr[i1][j1 + 1] == 'G':
							return 0
						elif arr[i1][j1 + 1] in nghbr:
							if c == 'N' or c == arr[i1][j1 + 1]:
								c = arr[i1][j1 + 1]
							else:
								return 0
				if c == 'N':
					if l == 1:
						count = count * 3 % (10 ** 9 + 7)
					else:
						count = count * 2 % (10 ** 9 + 7)
			elif arr[i][j] == 'G':
				if i != n - 1 and (arr[i + 1][j] == 'G' or arr[i + 1][j] in nghbr):
					return 0
				elif j != n - 1 and (arr[i][j + 1] == 'G' or arr[i][j + 1] in nghbr):
					return 0
				elif i != 0 and (arr[i - 1][j] == 'G' or arr[i - 1][j] in nghbr):
					return 0
				elif j != 0 and (arr[i][j - 1] == 'G' or arr[i][j - 1] in nghbr):
					return 0
			elif arr[i][j] == 'B':
				if i != n - 1 and arr[i + 1][j] == 'P':
					return 0
				elif j != n - 1 and arr[i][j + 1] == 'P':
					return 0
				elif i != 0 and arr[i - 1][j] == 'P':
					return 0
				elif j != 0 and arr[i][j - 1] == 'P':
					return 0
			elif arr[i][j] == 'P':
				if i != n - 1 and arr[i + 1][j] == 'B':
					return 0
				elif j != n - 1 and arr[i][j + 1] == 'B':
					return 0
				elif i != 0 and arr[i - 1][j] == 'B':
					return 0
				elif j != 0 and arr[i][j - 1] == 'B':
					return 0
	return count % (10 ** 9 + 7)
t = int(input())
for t1 in range(t):
	n = int(input())
	arr = [None] * n
	for i in range(n):
		arr[i] = [ch for ch in input()]
	print(getSpecies(arr, n) % (10 ** 9 + 7))


def connectedComponents(board):
	n = len(board)
	visited = [[False] * n for i in range(n)]
	for i in range(n):
		for j in range(n):
			if visited[i][j]:
				continue
			if board[i][j] == '?':
				yield component((i, j), board, visited)

def component(start, board, visited):
	size = 0
	bears = set()
	queue = [start]
	while queue:
		(i, j) = queue.pop()
		if visited[i][j]:
			continue
		what = board[i][j]
		if what == '.':
			continue
		if what == '?':
			visited[i][j] = True
			size += 1
			queue.extend(neighbours((i, j), board))
		else:
			bears.add(what)
	return (size, bears)

def neighbours(coord, board):
	(i, j) = coord
	if i > 0:
		yield (i - 1, j)
	if j > 0:
		yield (i, j - 1)
	n = len(board) - 1
	if i < n:
		yield (i + 1, j)
	if j < n:
		yield (i, j + 1)

def nSolutions(board):
	n = 1
	for (size, neighbears) in connectedComponents(board):
		if 'G' in neighbears or len(neighbears) == 2:
			return 0
		if len(neighbears) == 1:
			continue
		n = n * (3 if size == 1 else 2) % 1000000007
	return n

def stupid(board):
	n = len(board)
	bears = frozenset(('B', 'G', 'P'))
	for i in range(n):
		for j in range(n):
			x = board[i][j]
			if x not in bears:
				continue
			neighs = ()
			if i + 1 < n:
				neighs += ((i + 1, j),)
			if j + 1 < n:
				neighs += ((i, j + 1),)
			for (k, l) in neighs:
				y = board[k][l]
				if y == 'G' or (y in bears and x != y):
					return True
	return False
for testIdx in range(int(input())):
	n = int(input())
	board = list((input() for i in range(n)))
	if stupid(board):
		print('0')
	else:
		print(nSolutions(board))