MOD = 998244353 def main(): import sys input = sys.stdin.read().split() ptr = 0 H = int(input[ptr]); ptr +=1 W = int(input[ptr]); ptr +=1 K = int(input[ptr]); ptr +=1 grid = [] for _ in range(H): grid.append(input[ptr]) ptr +=1 # Initialize dp, pre_sum, diag_sum, diag_prefix dp = [[0]*(W+1) for _ in range(H+1)] pre_sum = [[0]*(W+1) for _ in range(H+1)] max_s = H + W diag_sum = [0]*(max_s + 2) diag_prefix = [0]*(max_s + 2) # Starting point dp[1][1] = 1 pre_sum[1][1] = 1 diag_sum[2] = 1 diag_prefix[2] = 1 for s in range(3, max_s +1): current_v = s for i in range(1, H+1): j = s - i if j < 1 or j > W: continue if i == 1 and j == 1: continue # Check if the current cell is blocked if grid[i-1][j-1] == '#': dp[i][j] = 0 pre_sum[i][j] = (pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]) % MOD continue # Compute pre_sum_i_j pre_sum_i_j = (pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1]) % MOD # Calculate v_min and v_max v_min = 2 v_max = s - K - 1 if v_max >= v_min: sum_diags = (diag_prefix[v_max] - diag_prefix[v_min-1]) % MOD else: sum_diags = 0 # Compute dp[i][j] dp_ij = (pre_sum_i_j - sum_diags) % MOD if dp_ij < 0: dp_ij += MOD dp[i][j] = dp_ij # Update pre_sum pre_sum[i][j] = (pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + dp_ij) % MOD # Update diag_sum diag_sum[current_v] = (diag_sum[current_v] + dp_ij) % MOD # Update diag_prefix if current_v >= 2: diag_prefix[current_v] = (diag_prefix[current_v-1] + diag_sum[current_v]) % MOD print(dp[H][W] % MOD) if __name__ == "__main__": main()