#include #ifdef LOCAL #include "./debug.cpp" #else #define debug(...) #define print_line #endif using namespace std; using ll = long long; const vector dx = {1, 0}; const vector dy = {0, 1}; int main() { int H, W; cin >> H >> W; vector S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } vector>> dp(H, vector>(W, vector(H + W + 1, 0))); dp[0][0][1] = 1; for (int x = 0; x < H; x++) { for (int y = 0; y < W; y++) { for (int i = 0; i <= H + W; i++) { for (int j = 0; j < 2; j++) { int nx = x + dx[j]; int ny = y + dy[j]; if (nx >= H || ny >= W) { continue; } if (S[nx][ny] == '#') { continue; } int ni = S[nx][ny] == 'o' ? 1 : -1; if (i + ni < 0) { continue; } dp[nx][ny][i + ni] += dp[x][y][i]; } } } } int ans = 0; for (int i = 0; i <= H + W; i++) { ans += dp[H - 1][W - 1][i]; } cout << ans << endl; }