问题

### Instructions: You are an expert Python programmer. You will be given a question (problem specification) and will generate a correct Python program that matches the specification and passes all tests. You will NOT return anything except for the program.
### Question:
This problem has a similar setting to Problem G. Differences in the problem statement are indicated in red.
There is a grid with H rows and W columns, where each cell is painted red or green.
Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
The color of cell (i,j) is represented by the character S_{i,j}, where S_{i,j} = . means cell (i,j) is red, and S_{i,j} = # means cell (i,j) is green.
The number of green connected components in the grid is the number of connected components in the graph with the vertex set being the green cells and the edge set being the edges connecting two adjacent green cells. Here, two cells (x,y) and (x',y') are considered adjacent when |x-x'| + |y-y'| = 1.
Consider choosing one red cell uniformly at random and repainting it green. Print the expected value of the number of green connected components in the grid after repainting, modulo 998244353.

What does "print the expected value modulo 998244353" mean?
It can be proved that the sought expected value is always rational.
Furthermore, the constraints of this problem guarantee that if that value is expressed as \frac{P}{Q} using two coprime integers P and Q, there is exactly one integer R such that R \times Q \equiv P \pmod{998244353} and 0 \leq R < 998244353. Print this R.

Input

The input is given from Standard Input in the following format:
H W
S_{1,1}S_{1,2}\ldotsS_{1,W}
S_{2,1}S_{2,2}\ldotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\ldotsS_{H,W}

Output

Print the answer.

Constraints


- 1 \leq H,W \leq 1000
- S_{i,j} = . or S_{i,j} = #.
- There is at least one (i,j) such that S_{i,j} = ..

Sample Input 1

3 3
##.
#.#
#..

Sample Output 1

499122178

If cell (1,3) is repainted green, the number of green connected components becomes 1.
If cell (2,2) is repainted green, the number of green connected components becomes 1.
If cell (3,2) is repainted green, the number of green connected components becomes 2.
If cell (3,3) is repainted green, the number of green connected components becomes 2.
Therefore, the expected value of the number of green connected components after choosing one red cell uniformly at random and repainting it green is (1+1+2+2)/4 = 3/2.

Sample Input 2

4 5
..#..
.###.
#####
..#..

Sample Output 2

598946613

Sample Input 3

3 4
#...
.#.#
..##

Sample Output 3

285212675

### Format: Read the inputs from stdin solve the problem and write the answer to stdout (do not directly test on the sample inputs). Enclose your code within delimiters as follows.
```python
# YOUR CODE HERE
```

### Answer: (use the provided format with backticks)

答案

模型 模型答案 正确答案
金声玉亮2.0 ```python
import sys
from collections import deque

MOD = 998244353

def count_green_components(grid, H, W):
def bfs(x, y):
q = deque([(x, y)])
grid[x][y] = '.'
while q:
cx, cy = q.popleft()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = cx + dx, cy + dy
if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '#':
grid[nx][ny] = '.'
q.append((nx, ny))

count = 0
for i in range(H):
for j in range(W):
if grid[i][j] == '#':
bfs(i, j)
count += 1
return count

def main():
input = sys.stdin.read
data = input().split()

H = int(data[0])
W = int(data[1])
grid = [list(data[i + 2]) for i in range(H)]

red_cells = []
for i in range(H):
for j in range(W):
if grid[i][j] == '.':
red_cells.append((i, j))

total_components = 0
for i, j in red_cells:
grid[i][j] = '#'
total_components += count_green_components([row[:] for row in grid], H, W)
grid[i][j] = '.'

expected_value = total_components / len(red_cells)
P, Q = expected_value.as_integer_ratio()
R = (P * pow(Q, MOD - 2, MOD)) % MOD
print(R)

if __name__ == "__main__":
main()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
deepseek-r1

```python
import sys
from collections import deque

MOD = 998244353

def main():
H, W = map(int, sys.stdin.readline().split())
grid = [sys.stdin.readline().strip() for _ in range(H)]

component = [[-1] * W for _ in range(H)]
current_component = 0
dirs = [(-1,0), (1,0), (0,-1), (0,1)]

for i in range(H):
for j in range(W):
if grid[i][j] == '#' and component[i][j] == -1:
q = deque()
q.append((i, j))
component[i][j] = current_component
while q:
x, y = q.popleft()
for dx, dy in dirs:
nx = x + dx
ny = y + dy
if 0 <= nx < H and 0 <= ny < W:
if grid[nx][ny] == '#' and component[nx][ny] == -1:
component[nx][ny] = current_component
q.append((nx, ny))
current_component += 1

C_initial = current_component
R = 0
S_sum = 0

for i in range(H):
for j in range(W):
if grid[i][j] == '.':
R += 1
adjacent_components = set()
for dx, dy in dirs:
nx = i + dx
ny = j + dy
if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '#':
adjacent_components.add(component[nx][ny])
k = len(adjacent_components)
S_sum += (C_initial + 1 - k)

inv_R = pow(R, MOD-2, MOD) if R != 0 else 0
print((S_sum * inv_R) % MOD)

if __name__ == "__main__":
main()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading

def main():
import sys
import math
sys.setrecursionlimit(1 << 25)
mod = 998244353

H, W = map(int, sys.stdin.readline().split())
grid = []
for _ in range(H):
grid.append(list(sys.stdin.readline().strip()))

N = H * W
parent = [ -1 ] * N # parent[i] = parent index if i is green, -1 if red

# Initialize parent array for green cells
for x in range(H):
for y in range(W):
idx = x * W + y
if grid[x][y] == '#':
parent[idx] = idx

# Union adjacent green cells
def find(u):
if parent[u] != u:
parent[u] = find(parent[u])
return parent[u]

def union(u, v):
pu = find(u)
pv = find(v)
if pu != pv:
parent[pu] = pv

for x in range(H):
for y in range(W):
idx = x * W + y
if grid[x][y] == '#':
for dx, dy in [ (0,1), (1,0), (-1,0), (0,-1) ]:
nx, ny = x + dx, y + dy
if 0 <= nx < H and 0 <= ny < W:
nidx = nx * W + ny
if grid[nx][ny] == '#':
union(idx, nidx)

# Compute initial number of green components C0
roots = set()
for x in range(H):
for y in range(W):
idx = x * W + y
if grid[x][y] == '#':
root = find(idx)
roots.add(root)
C0 = len(roots)

red_cells = []
for x in range(H):
for y in range(W):
if grid[x][y] == '.':
red_cells.append((x,y))

N_red = len(red_cells)
sum_C_r = 0

for x, y in red_cells:
Adj = set()
for dx, dy in [ (0,1), (1,0), (-1,0), (0,-1) ]:
nx, ny = x + dx, y + dy
if 0 <= nx < H and 0 <= ny < W:
if grid[nx][ny] == '#':
nidx = nx * W + ny
nroot = find(nidx)
Adj.add(nroot)
k = len(Adj)
if k == 0:
C_r = C0 + 1
else:
C_r = C0 - (k - 1)
sum_C_r += C_r

P = sum_C_r
Q = N_red

# Compute R such that R * Q ≡ P mod mod
# R = P * Q_inv mod mod
Q_inv = pow(Q, mod - 2, mod)
R = P * Q_inv % mod
print(R)

threading.Thread(target=main).start()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
gpt-4o-2024-08-06 ```python
# YOUR CODE HERE
import sys
from collections import deque

MOD = 998244353

def find_connected_components(grid, H, W):
visited = [[False] * W for _ in range(H)]
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

def bfs(start_i, start_j):
queue = deque([(start_i, start_j)])
visited[start_i][start_j] = True
while queue:
i, j = queue.popleft()
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < H and 0 <= nj < W and not visited[ni][nj] and grid[ni][nj] == '#':
visited[ni][nj] = True
queue.append((ni, nj))

component_count = 0
for i in range(H):
for j in range(W):
if grid[i][j] == '#' and not visited[i][j]:
bfs(i, j)
component_count += 1

return component_count

def mod_inverse(a, m):
# Using Fermat's Little Theorem for modular inverse
return pow(a, m - 2, m)

def main():
input = sys.stdin.read
data = input().split()

H = int(data[0])
W = int(data[1])
grid = data[2:H+2]

initial_components = find_connected_components(grid, H, W)

red_cells = []
for i in range(H):
for j in range(W):
if grid[i][j] == '.':
red_cells.append((i, j))

total_red_cells = len(red_cells)
expected_value_sum = 0

for i, j in red_cells:
grid[i] = grid[i][:j] + '#' + grid[i][j+1:]
new_components = find_connected_components(grid, H, W)
expected_value_sum += new_components
grid[i] = grid[i][:j] + '.' + grid[i][j+1:]

P = expected_value_sum
Q = total_red_cells

Q_inv = mod_inverse(Q, MOD)
result = (P * Q_inv) % MOD

print(result)

main()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
DeepSeek-Coder-V2-Lite-Instruct ```python
# YOUR CODE HERE
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
Meta-Llama-3.1-405B-Instruct-Turbo ```python
import sys
input = sys.stdin.readline

mod = 998244353

def find(x):
while Group[x] != x:
x=Group[x]
return x

def Union(x,y):
if find(x) != find(y):
if Nodes[find(x)] < Nodes[find(y)]:

Nodes[find(y)] += Nodes[find(x)]
Nodes[find(x)] = 0
Group[find(x)] = find(y)

else:
Nodes[find(x)] += Nodes[find(y)]
Nodes[find(y)] = 0
Group[find(y)] = find(x)

h,w = map(int,input().split())
s = [list(input().strip()) for i in range(h)]

Group = [i for i in range(h*w)]
Nodes = [1]*(h*w)

for i in range(h):
for j in range(w):
if s[i][j] == "#":
if i > 0 and s[i-1][j] == "#":
Union(i*w+j,(i-1)*w+j)
if j > 0 and s[i][j-1] == "#":
Union(i*w+j,i*w+j-1)

ans = 0
for i in range(h):
for j in range(w):
if s[i][j] == ".":
tmp = 1
if i > 0 and s[i-1][j] == "#":
tmp += (find((i-1)*w+j) != find(i*w+j))
if j > 0 and s[i][j-1] == "#":
tmp += (find(i*w+j-1) != find(i*w+j))
if i < h-1 and s[i+1][j] == "#":
tmp += (find((i+1)*w+j) != find(i*w+j))
if j < w-1 and s[i][j+1] == "#":
tmp += (find(i*w+j+1) != find(i*w+j))
ans += tmp

cnt = 0
for i in range(h):
for j in range(w):
if s[i][j] == ".":
cnt += 1

ans = (ans + cnt * (h*w-cnt)) % mod
ans = ans * pow(cnt,mod-2,mod) % mod

print(ans)
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
Meta-Llama-3.1-70B-Instruct-Turbo ```python
import sys
input = sys.stdin.readline

mod = 998244353

def find(x):
while Group[x] != x:
x = Group[x]
return x

def Union(x, y):
if find(x) != find(y):
if Nodes[find(x)] < Nodes[find(y)]:

Nodes[find(y)] += Nodes[find(x)]
Nodes[find(x)] = 0
Group[find(x)] = find(y)

else:
Nodes[find(x)] += Nodes[find(y)]
Nodes[find(y)] = 0
Group[find(y)] = find(x)

H, W = map(int, input().split())
S = [list(input().rstrip()) for _ in range(H)]

Group = [i for i in range(H*W)]
Nodes = [1]*(H*W)

for h in range(H):
for w in range(W):
if S[h][w] == '#':
if h > 0 and S[h-1][w] == '#':
Union(h*w + w, (h-1)*w + w)
if w > 0 and S[h][w-1] == '#':
Union(h*w + w, h*w + w-1)

Components = set()
for h in range(H):
for w in range(W):
if S[h][w] == '#':
Components.add(find(h*w + w))

Red = []
for h in range(H):
for w in range(W):
if S[h][w] == '.':
Neigh = set()
if h > 0 and S[h-1][w] == '#':
Neigh.add(find((h-1)*w + w))
if w > 0 and S[h][w-1] == '#':
Neigh.add(find(h*w + w-1))
if h < H-1 and S[h+1][w] == '#':
Neigh.add(find((h+1)*w + w))
if w < W-1 and S[h][w+1] == '#':
Neigh.add(find(h*w + w+1))
Red.append(Neigh)

N = len(Red)
Ans = 0
for i in range(N):
if len(Red[i]) == 0:
Ans += 1
elif len(Red[i]) == 1:
Ans += 1
else:
flag = True
for j in Red[i]:
if Nodes[j] > 1:
flag = False
break
if flag:
Ans += len(Red[i]) - 1

Denom = pow(N, mod-2, mod)
Ans = Ans*Denom%mod
print(Ans)
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
Qwen2-72B-Instruct ```python
from collections import defaultdict, deque
import sys
input = sys.stdin.readline

MOD = 998244353

def modinv(a):
b = MOD
u = 1
v = 0
while b:
t = a // b
a -= t * b
u -= t * v
a, b = b, a
u, v = v, u
u %= MOD
return u

class UnionFind:
def __init__(self, n):
self.n = n
self.parents = [-1] * n

def find(self, x):
if self.parents[x] < 0:
return x
else:
self.parents[x] = self.find(self.parents[x])
return self.parents[x]

def union(self, x, y):
x = self.find(x)
y = self.find(y)

if x == y:
return

if self.parents[x] > self.parents[y]:
x, y = y, x

self.parents[x] += self.parents[y]
self.parents[y] = x

def size(self, x):
return -self.parents[self.find(x)]

def same(self, x, y):
return self.find(x) == self.find(y)

def members(self, x):
root = self.find(x)
return [i for i in range(self.n) if self.find(i) == root]

def roots(self):
return [i for i, x in enumerate(self.parents) if x < 0]

def group_count(self):
return len(self.roots())

def all_group_members(self):
group_members = defaultdict(list)
for member in range(self.n):
group_members[self.find(member)].append(member)
return group_members

def __str__(self):
return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
queue.extend(graph[vertex] - visited)
return visited

def main():
H, W = map(int, input().split())
S = [list(input().strip()) for _ in range(H)]

uf = UnionFind(H*W)
for i in range(H):
for j in range(W):
if S[i][j] == '#':
for di, dj in [(0, 1), (1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '#':
uf.union(i*W+j, ni*W+nj)

groups = uf.all_group_members()
group_sizes = [len(group) for group in groups.values()]

red_cells = sum(1 for i in range(H) for j in range(W) if S[i][j] == '.')
total_groups = len(group_sizes)

ans = 0
for i in range(H):
for j in range(W):
if S[i][j] == '.':
new_groups = 0
for di, dj in [(0, 1), (1, 0)]:
ni, nj = i + di, j + dj
if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == '#':
new_groups += 1
group_id = uf.find(ni*W+nj)
new_groups += group_sizes[group_id] - 1

ans += (total_groups + new_groups) % MOD

ans *= modinv(red_cells)
ans %= MOD

print(ans)

if __name__ == '__main__':
main()
```
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
baichuan4 ```python
import sys
from collections import deque

MOD = 998244353

def bfs(grid, start_row, start_col):
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = deque([(start_row, start_col)])
visited = set([(start_row, start_col)])

while queue:
row, col = queue.popleft()
for dr, dc in directions:
new_row, new_col = row + dr, col + dc
if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]) and grid[new_row][new_col] == '#' and (new_row, new_col) not in visited:
visited.add((new_row, new_col))
queue.append((new_row, new_col))
return visited

def count_components(grid):
components = 0
visited = set()
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '#' and (i, j) not in visited:
components += 1
visited.update(bfs(grid, i, j))
return components

def main():
H, W = map(int, sys.stdin.readline().split())
grid = [list(sys.stdin.readline().strip()) for _ in range(H)]

red_cells = [(i, j) for i in range(H) for j in range(W) if grid[i][j] == '.']

expected_value = 0
for i, j in red_cells:
grid[i][j] = '#' # Repaint the cell green
components = count_components(grid)
expected_value = (expected_value + components) % MOD
grid[i][j] = '.' # Revert the change

expected_value = expected_value * pow(len(red_cells), MOD - 2, MOD) % MOD
print(expected_value)

if __name__ == "__main__":
main()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
doubao ```python
from collections import deque

def bfs(grid, i, j):
q = deque([(i, j)])
grid[i][j] = '#'
count = 1
while q:
x, y = q.popleft()
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.':
q.append((nx, ny))
grid[nx][ny] = '#'
count += 1
return count

H, W = map(int, input().split())
grid = [list(input()) for _ in range(H)]

red_cells = []
for i in range(H):
for j in range(W):
if grid[i][j] == '.':
red_cells.append((i, j))

total = 0
for r, c in red_cells:
new_grid = [row[:] for row in grid]
new_grid[r][c] = '#'
components = []
for i in range(H):
for j in range(W):
if new_grid[i][j] == '.':
components.append(bfs(new_grid, i, j))
total += sum(components) / len(components) if components else 0

print(total % 998244353)
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
gpto1 ```python
# YOUR CODE HERE
import sys
import threading

def main():
import sys
import math
sys.setrecursionlimit(1 << 25)
mod = 998244353

H, W = map(int, sys.stdin.readline().split())
grid = []
for _ in range(H):
grid.append(list(sys.stdin.readline().strip()))

N = H * W
parent = [ -1 ] * N # parent[i] = parent index if i is green, -1 if red

# Initialize parent array for green cells
for x in range(H):
for y in range(W):
idx = x * W + y
if grid[x][y] == '#':
parent[idx] = idx

# Union adjacent green cells
def find(u):
if parent[u] != u:
parent[u] = find(parent[u])
return parent[u]

def union(u, v):
pu = find(u)
pv = find(v)
if pu != pv:
parent[pu] = pv

for x in range(H):
for y in range(W):
idx = x * W + y
if grid[x][y] == '#':
for dx, dy in [ (0,1), (1,0), (-1,0), (0,-1) ]:
nx, ny = x + dx, y + dy
if 0 <= nx < H and 0 <= ny < W:
nidx = nx * W + ny
if grid[nx][ny] == '#':
union(idx, nidx)

# Compute initial number of green components C0
roots = set()
for x in range(H):
for y in range(W):
idx = x * W + y
if grid[x][y] == '#':
root = find(idx)
roots.add(root)
C0 = len(roots)

red_cells = []
for x in range(H):
for y in range(W):
if grid[x][y] == '.':
red_cells.append((x,y))

N_red = len(red_cells)
sum_C_r = 0

for x, y in red_cells:
Adj = set()
for dx, dy in [ (0,1), (1,0), (-1,0), (0,-1) ]:
nx, ny = x + dx, y + dy
if 0 <= nx < H and 0 <= ny < W:
if grid[nx][ny] == '#':
nidx = nx * W + ny
nroot = find(nidx)
Adj.add(nroot)
k = len(Adj)
if k == 0:
C_r = C0 + 1
else:
C_r = C0 - (k - 1)
sum_C_r += C_r

P = sum_C_r
Q = N_red

# Compute R such that R * Q ≡ P mod mod
# R = P * Q_inv mod mod
Q_inv = pow(Q, mod - 2, mod)
R = P * Q_inv % mod
print(R)

threading.Thread(target=main).start()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
kimi ```python
from collections import deque

def bfs(y, x):
global ans, total, grid, used, mod
q = deque()
q.append((y, x))
used[y, x] = True
cnt = 1
tmp = 0
while q:
(cy, cx) = q.popleft()
for (dy, dx) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
ny = cy + dy
nx = cx + dx
if 0 <= ny < h and 0 <= nx < w and grid[ny][nx] == '#' and (not used[ny, nx]):
q.append((ny, nx))
used[ny, nx] = True
cnt += 1
if grid[cy][cx] == '#':
tmp += 1
ans = (ans + (cnt - tmp) * total + tmp - 1) % mod
total = total * cnt % mod

def main():
global ans, total, grid, used, mod, h, w
mod = 998244353
(h, w) = map(int, input().split())
grid = [list(input()) for _ in range(h)]
total = h * w + 1
ans = 0
used = {}
for i in range(h):
for j in range(w):
if grid[i][j] == '#':
used[i, j] = False
bfs(i, j)
else:
used[i, j] = True
print(ans * pow(total, mod - 2, mod) % mod)
main()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
minimax ```python
from collections import deque

MOD = ***

def bfs(grid, i, j):
if grid[i][j] != '#':
return 0
queue = deque([(i, j)])
grid[i][j] = 'X'
count = 1
while queue:
x, y = queue.popleft()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == '#':
grid[nx][ny] = 'X'
count += 1
queue.append((nx, ny))
return count

def solve(H, W, grid):
total_components = 0
for i in range(H):
for j in range(W):
if grid[i][j] == '#':
total_components += bfs(grid, i, j) - 1
red_cells = sum(row.count('.') for row in grid)
expected		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
wenxinyiyan ```python
MOD = 998244353

def main():
H, W = map(int, input().split())
grid = [input() for _ in range(H)]

# Count the total number of red cells
total_red = 0
for row in grid:
total_red += row.count('.')

# Initialize the components count for each repainting case
components_count = [0] * (total_red + 1)

# Helper function to perform DFS and count components
def dfs(i, j, visited, component_id):
if i < 0 or i >= H or j < 0 or j >= W or grid[i][j] != '#' or visited[i][j]:
return
visited[i][j] = True
components_count[component_id] += 1
dfs(i - 1, j, visited, component_id) # Up
dfs(i + 1, j, visited, component_id) # Down
dfs(i, j - 1, visited, component_id) # Left
dfs(i, j + 1, visited, component_id) # Right

# Count the initial number of green components
visited = [[False] * W for _ in range(H)]
component_id = 0
for i in range(H):
for j in range(W):
if grid[i][j] == '#' and not visited[i][j]:
component_id += 1
dfs(i, j, visited, component_id)
initial_components = component_id

# Try repainting each red cell and count the resulting components
for i in range(H):
for j in range(W):
if grid[i][j] == '.':
# Repaint the cell to green
grid[i][j] = '#'

# Reset visited and component_id
visited = [[False] * W for _ in range(H)]
component_id = 0

# Perform DFS to count components after repainting
for x in range(H):
for y in range(W):
if grid[x][y] == '#' and not visited[x][y]:
component_id += 1
dfs(x, y, visited, component_id)

# Update the components count for this repainting case
components_count[component_id] += 1

# Restore the cell to red for the next iteration
grid[i][j] = '.'

# Calculate the expected value
expected_value = 0
for i in range(1, total_red + 1):
expected_value = (expected_value + components_count[i] * i) % MOD
expected_value = (expected_value * pow(total_red, MOD - 2, MOD)) % MOD

# Adjust the expected value by adding the initial components
expected_value = (expected_value + initial_components) % MOD

print(expected_value)

# Execute the main function
if __name__ == '__main__':
main()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
zhipu ```python
import sys
input = sys.stdin.read
sys.setrecursionlimit(10**6)
MOD = 998244353

def main():
data = input().split()
H = int(data[0])
W = int(data[1])
grid = [list(data[i + 2]) for i in range(H)]

def dfs(x, y, visited):
stack = [(x, y)]
while stack:
cx, cy = stack.pop()
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = cx + dx, cy + dy
if 0 <= nx < H and 0 <= ny < W and not visited[nx][ny] and grid[nx][ny] == '#':
visited[nx][ny] = True
stack.append((nx, ny))

visited = [[False] * W for _ in range(H)]
green_components = 0
for i in range(H):
for j in range(W):
if grid[i][j] == '#' and not visited[i][j]:
visited[i][j] = True
dfs(i, j, visited)
green_components += 1

red_cells = []
for i in range(H):
for j in range(W):
if grid[i][j] == '.':
red_cells.append((i, j))

def count_adjacent_green(x, y):
count = 0
for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '#':
count += 1
return count

numerator = 0
denominator = len(red_cells)
inv_denominator = pow(denominator, MOD - 2, MOD)

for x, y in red_cells:
adjacent_green = count_adjacent_green(x, y)
if adjacent_green == 0:
# This red cell is isolated, adding a new component
numerator = (numerator + green_components + 1) % MOD
else:
# This red cell connects existing components
numerator = (numerator + green_components - adjacent_green + 1) % MOD

result = (numerator * inv_denominator) % MOD
print(result)

if __name__ == "__main__":
main()
```		 [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]
deepseek-v3 Error code: 400 - {'error': {'code': 'RequestTimeOut', 'param': None, 'message': 'Request timed out, please try again later.', 'type': 'RequestTimeOut'}, 'id': 'chatcmpl-6299d4e0-c77b-93e4-bb2b-3583c44a955c', 'request_id': '6299d4e0-c77b-93e4-bb2b-3583c44a955c'} [{"input": "3 3\n##.\n#.#\n#..\n", "output": "499122178\n", "testtype": "stdin"}, {"input": "4 5\n..#..\n.###.\n#####\n..#..\n", "output": "598946613\n", "testtype": "stdin"}, {"input": "3 4\n#...\n.#.#\n..##\n", "output": "285212675\n", "testtype": "stdin"}]