#include #ifdef LOCAL #include "./debug.cpp" #else #define debug(...) #define print_line #endif using namespace std; using ll = long long; int main() { int H, W; cin >> H >> W; vector S(H); for (int i = 0; i < H; i++) { cin >> S[i]; } vector T(H + W - 2, 0); for (int i = H - 1; i < H + W - 2; i++) { T[i] = 1; } int ans = 0; do { int cnt = 0, x = 0, y = 0; bool ok = true; for (int i = 0; i < H + W - 2; i++) { if (x >= H || y >= H || S[x][y] == '#') { ok = false; break; } if (S[x][y] == 'o') { cnt++; } else if (S[x][y] == 'x' && cnt > 0) { cnt--; } else { ok = false; break; } if (T[i] == 0) { x++; } else { y++; } } if (ok) { ans++; } } while (next_permutation(T.begin(), T.end())); cout << ans << endl; }