#include using namespace std; const long long MOD = 998244353; int main(){ int H, W, K; cin >> H >> W >> K; vector> C(H, vector(W)); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ cin >> C[i][j]; } } vector> R(H + W - 1); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ R[i + j].push_back(i); } } vector> dp(H, vector(W, 0)); vector> tmp(H, vector(W, 0)); vector> sum1(H + 1, vector(W, 0)); vector> sum2(H, vector(W + 1, 0)); vector> sum(H + W - 1); dp[0][0] = 1; sum1[1][0] = 1; sum2[0][1] = 1; sum[0] = {0, 1}; for (int i = 1; i < H + W - 1; i++){ int cnt = R[i].size(); sum[i].resize(cnt + 1); sum[i][0] = 0; for (int j = 0; j < cnt; j++){ int r = R[i][j], c = i - r; if (r > 0){ tmp[r][c] = tmp[r - 1][c] + dp[r - 1][c]; tmp[r][c] += sum2[r][c] - sum2[r][max(c - K, 0)]; if (i > K){ int p1 = lower_bound(R[i - K - 1].begin(), R[i - K - 1].end(), max(r - K - 1, 0)) - R[i - K - 1].begin(); int p2 = lower_bound(R[i - K - 1].begin(), R[i - K - 1].end(), r) - R[i - K - 1].begin(); tmp[r][c] -= sum[i - K - 1][p2] - sum[i - K - 1][p1]; } } else { tmp[r][c] = tmp[r][c - 1] + dp[r][c - 1]; tmp[r][c] += sum1[r][c] - sum1[max(r - K, 0)][c]; if (i > K){ int p1 = lower_bound(R[i - K - 1].begin(), R[i - K - 1].end(), max(r - K, 0)) - R[i - K - 1].begin(); int p2 = lower_bound(R[i - K - 1].begin(), R[i - K - 1].end(), r + 1) - R[i - K - 1].begin(); tmp[r][c] -= sum[i - K - 1][p2] - sum[i - K - 1][p1]; } } tmp[r][c] %= MOD; if (tmp[r][c] < 0){ tmp[r][c] += MOD; } if (C[r][c] == '.'){ dp[r][c] = tmp[r][c]; } sum1[r + 1][c] = (sum1[r][c] + dp[r][c]) % MOD; sum2[r][c + 1] = (sum2[r][c] + dp[r][c]) % MOD; sum[i][j + 1] = (sum[i][j] + dp[r][c]) % MOD; } } cout << dp[H - 1][W - 1] << endl; }