MOD = 998244353 def main(): H, W, K, C = open(0).read().split(maxsplit=3) H, W, K = int(H), int(W), int(K) dp = [0] * (H * W) stair = [0] * (H * W) dacc = [0] * (H * W) for i in range(H): hacc = [0] * W for j in range(W): x = 0 if i == 0 and j == 0: dp[0] += 1 else: if i > 0: x += stair[(i - 1) * W + j] if j > 0: x += hacc[j - 1] if j >= K + 1: x -= hacc[j - K - 1] p = max(0, K - j) if i >= p + 1: x -= dacc[(i - p - 1) * W + j + p - K] if i >= K + 2 and j + 1 < W: x += dacc[(i - K - 2) * W + j + 1] x %= MOD if C[i * (W + 1) + j] == ".": dp[i * W + j] = x stair[i * W + j] = (x + dp[i * W + j]) % MOD dacc[i * W + j] = dp[i * W + j] if i > 0 and j + 1 < W: dacc[i * W + j] = (dacc[i * W + j] + dacc[(i - 1) * W + j + 1]) % MOD hacc[j] = dp[i * W + j] if j > 0: hacc[j] = (hacc[j] + hacc[j - 1]) % MOD print(dp[-1]) if __name__ == "__main__": main()