/* -*- coding: utf-8 -*- * * 2430.cc: No.2430 Damage Zone - yukicoder */ #include #include using namespace std; /* constant */ const int MAX_H = 100; const int MAX_W = 100; const int MAX_K = MAX_H + MAX_W; const int MOD = 998244353; /* typedef */ /* global variables */ char fs[MAX_H][MAX_W + 4]; int dp[MAX_H][MAX_W][MAX_K]; /* subroutines */ inline void addmod(int &a, int b) { a = (a + b) % MOD; } /* main */ int main() { int h, w, k; scanf("%d%d%d", &h, &w, &k); for (int i = 0; i < h; i++) scanf("%s", fs[i]); dp[0][0][0] = 1; for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) if (fs[i][j] != '#') { if (i + 1 < h && fs[i + 1][j] != '#') { if (fs[i + 1][j] == '.') for (int l = 0; l < k; l++) addmod(dp[i + 1][j][l], dp[i][j][l]); else for (int l = 0; l + 1 < k; l++) addmod(dp[i + 1][j][l + 1], dp[i][j][l]); } if (j + 1 < w && fs[i][j + 1] != '#') { if (fs[i][j + 1] == '.') for (int l = 0; l < k; l++) addmod(dp[i][j + 1][l], dp[i][j][l]); else for (int l = 0; l + 1 < k; l++) addmod(dp[i][j + 1][l + 1], dp[i][j][l]); } } int sum = 0; for (int l = 0; l < k; l++) addmod(sum, dp[h - 1][w - 1][l]); printf("%d\n", sum); return 0; }