MOD = 998244353 H, W, K = map(int, input().split()) grid = [input().strip() for _ in range(H)] # Initialize DP and prefix sums dp = [[0] * (W + 1) for _ in range(H + 1)] row_prefix = [[0] * (W + 1) for _ in range(H + 1)] prefix = [[0] * (W + 1) for _ in range(H + 1)] # Base case: starting cell (1,1) if grid[0][0] == '.': dp[1][1] = 1 row_prefix[1][1] = 1 prefix[1][1] = 1 for i in range(1, H + 1): for j in range(1, W + 1): if i == 1 and j == 1: continue # already initialized if grid[i-1][j-1] == '#': dp[i][j] = 0 else: S = i + j - K T = S - 1 # Calculate sum_rect using prefix sums sum_rect = (prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]) % MOD sum_lower = 0 # Iterate over x from 1 to i for x in range(1, i + 1): y_max = T - x if y_max < 1: continue if y_max > j: y_max = j sum_lower = (sum_lower + row_prefix[x][y_max]) % MOD dp[i][j] = (sum_rect - sum_lower) % MOD # Update row_prefix and prefix row_prefix[i][j] = (row_prefix[i][j-1] + dp[i][j]) % MOD prefix[i][j] = (prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + dp[i][j]) % MOD print(dp[H][W] % MOD)