MOD = 998244353 H, W, K = map(int, input().split()) grid = [input().strip() for _ in range(H)] dp = [[0] * (W + 1) for _ in range(H + 1)] dp[1][1] = 1 if grid[0][0] == '.' else 0 # Initialize row_prefix for each row row_prefix = [[0] * (W + 1) for _ in range(H + 1)] for i in range(1, H + 1): current_prefix = [0] * (W + 1) for j in range(1, W + 1): current_prefix[j] = (current_prefix[j-1] + dp[i][j]) % MOD row_prefix[i] = current_prefix for i in range(1, H + 1): current_row_prefix = [0] * (W + 1) for j in range(1, W + 1): if i == 1 and j == 1: current_row_prefix[j] = dp[i][j] continue if grid[i-1][j-1] == '#': dp[i][j] = 0 current_row_prefix[j] = (current_row_prefix[j-1] + dp[i][j]) % MOD continue total = 0 for a in range(0, min(K, i-1) + 1): x = i - a remaining = K - a if remaining < 0: continue min_j = max(1, j - remaining) if min_j > j: continue if x < 1: continue if x < i: # Use precomputed row_prefix for previous rows sum_val = (row_prefix[x][j] - row_prefix[x][min_j - 1]) % MOD else: # Current row, use current_row_prefix which is built up to j-1 sum_val = (current_row_prefix[j-1] - (current_row_prefix[min_j - 1] if min_j > 1 else 0)) % MOD total = (total + sum_val) % MOD dp[i][j] = total % MOD current_row_prefix[j] = (current_row_prefix[j-1] + dp[i][j]) % MOD # Update the row_prefix for this row after processing all columns row_prefix[i] = current_row_prefix print(dp[H][W] % MOD)