// No.226 0-1パズル #include #include #include using namespace std; const int MOD = 1'000'000'007; int main() { int H, W; cin >> H >> W; vector S(H); for (int i = 0; i < H; ++i) cin >> S[i]; int res = 0; for (int bit = 0; bit < (1 << W); ++bit) { vector tmp = S; int num = 1; auto check = [&](int i, int j) { int cnt0 = 0, cnt1 = 0, cntq = 0; vector> qidxlst; for (int row = i; row <= i + 1; ++row) { for (int col = j; col <= j + 1; ++col) { if (tmp[row][col] - '0' == 0) ++cnt0; if (tmp[row][col] - '0' == 1) ++cnt1; if (tmp[row][col] == '?') { ++cntq; qidxlst.push_back(make_pair(row, col)); } } } if (cntq > max(cnt0, cnt1)) return true; if (cnt0 < cnt1) { cnt0 += cntq; for (auto [row, col]: qidxlst) { tmp[row][col] = '0'; } } if (cnt1 < cnt0) { cnt1 += cntq; for (auto [row, col]: qidxlst) { tmp[row][col] = '1'; } } return cnt0 == cnt1; }; bool flag = false; for (int j = 0; j < W; ++j) { if (tmp[0][j] == '?') { tmp[0][j] = ((bit >> (W - j - 1)) & 1) + '0'; } else { if (((bit >> (W - j - 1)) & 1) != (tmp[0][j] - '0')) { flag = true; break; } } } if (flag) continue; for (int i = 0; i < H - 1; ++i) { for (int j = 0; j < W - 1; ++j) { if (!check(i, j)) { flag = true; break; } } if (flag) break; bool flag2 = true; for (int j = 0; j < W; ++j) { if (tmp[i + 1][j] != '?') flag2 = false; } if (flag2) num = 2; } if (flag) continue; res = (res + num) % MOD; } cout << res << endl; }