package main import . "fmt" func main() { var h,w,k int Scan(&h,&w,&k) s := make([]string, h) for i := range s { Scan(&s[i]) } dp := make([][][]int, h+w+2) for i := range dp { dp[i] = make([][]int, h) for j := range dp[i] { dp[i][j] = make([]int, w) } } visited := make([][]bool, h) for i := range visited { visited[i] = make([]bool, w) } const Mod = 998244353 dp[0][0][0] = 1 cur := []int{0,0} for i := 0; i < h+w+1; i++ { tmp := []int{} for len(cur) > 0 { l := len(cur) y, x := cur[l-2], cur[l-1] cur = cur[:l-2] if x + 1 < w { switch s[y][x+1] { case '.': for j := 0; j <= i; j++ { dp[j][y][x+1] += dp[j][y][x] dp[j][y][x+1] %= Mod } if !visited[y][x+1] { visited[y][x+1] = true tmp = append(tmp, y, x+1) } case 'o': for j := 0; j <= i && j+1 < k; j++ { dp[j+1][y][x+1] += dp[j][y][x] dp[j+1][y][x+1] %= Mod } if !visited[y][x+1] { visited[y][x+1] = true tmp = append(tmp, y, x+1) } } } if y + 1 < h { switch s[y+1][x] { case '.': for j := 0; j <= i; j++ { dp[j][y+1][x] += dp[j][y][x] dp[j][y+1][x] %= Mod } if !visited[y+1][x] { visited[y+1][x] = true tmp = append(tmp, y+1, x) } case 'o': for j := 0; j <= i && j+1 < k; j++ { dp[j+1][y+1][x] += dp[j][y][x] dp[j+1][y+1][x] %= Mod } if !visited[y+1][x] { visited[y+1][x] = true tmp = append(tmp, y+1, x) } } } } cur = tmp } ans := 0 for i := 0; i < k; i++ { ans += dp[i][h-1][w-1] ans %= Mod } Println(ans) }