#include #include using namespace std; using namespace atcoder; using ll = long long; #define rep(i, s, n) for(int i = s; i < (int)(n); i++) #define repr(i, s, n) for(int i = ((int)(n) - 1); i >= s; i--) #define sz(x) ((int)(x).size()) int h, w, ans; vector a; #define ij_no(i, j) ((int) (i) * w + (int) (j)) #define no_i(no) ((int) no / w) #define no_j(no) ((int) no % w) bool frame_in(int ni, int nj, int h, int w){ if(0 <= ni && ni < h && 0 <= nj && nj < w) return true; else return false; } void dfs(int v, int jewel, int &ans){ if(a[v] == '#') return ; else if(a[v] == 'o') jewel ++; else jewel --; if(jewel < 0) return ; if(v == h * w - 1) ans ++; int nxi = no_i(v), nxj = no_j(v) + 1; if(frame_in(nxi, nxj, h, w)) dfs(ij_no(nxi, nxj), ans, jewel); nxi = no_i(v) + 1, nxj = no_j(v); if(frame_in(nxi, nxj, h, w)) dfs(ij_no(nxi, nxj), ans, jewel); } int main(){ cin >> h >> w; a.resize (h * w); rep(i, 0, h * w){ cin >> a[i]; } ans = 0; dfs(0, 0, ans); cout << ans << endl; }