#include using namespace std; #define rep(i, n) for(int i=0; i #include int main() { int H, W; cin >> H >> W; vector grid(H); rep(i, H) { cin >> grid[i]; } vector>> dp(H, vector>(W, vector(105, 0))); dp[0][0][1] = 1; set> s; s.insert({ 0,0,0 }); while (!s.empty()) { vector v = *begin(s); vector now = { v[1], v[2] }; s.erase(v); if (grid[now[0]][now[1]] == '#') { continue; } if (now[0] < H - 1 && grid[now[0] + 1][now[1]] == 'o') { rep(i, 101) { dp[now[0] + 1][now[1]][i + 1] += dp[now[0]][now[1]][i]; } s.insert({ now[0] + now[1] + 1, now[0] + 1, now[1] }); } else if (now[0] < H - 1 && grid[now[0] + 1][now[1]] == 'x') { for (int i = 1; i <= 100; i++) { dp[now[0] + 1][now[1]][i - 1] += dp[now[0]][now[1]][i]; } s.insert({ now[0] + now[1] + 1, now[0] + 1, now[1] }); } if (now[1] < W - 1 && grid[now[0]][now[1]+1] == 'o') { rep(i, 101) { dp[now[0]][now[1]+1][i + 1] += dp[now[0]][now[1]][i]; } s.insert({ now[0] + now[1] + 1, now[0], now[1]+1 }); } else if (now[1] < W - 1 && grid[now[0]][now[1]+1] == 'x') { for (int i = 1; i <= 100; i++) { dp[now[0]][now[1]+1][i - 1] += dp[now[0]][now[1]][i]; } s.insert({ now[0] + now[1] + 1, now[0], now[1]+1 }); } } int ans = 0; rep(i, 101) { ans += dp[H - 1][W - 1][i]; } cout << ans << endl; }