左上から順に一マスずつ \(0\) か \(1\) を書き込むことで、数えるべきグリッドをすべて生成しましょう。次の値を考えます。

• \(\mathrm{dp[i][j][flag][mask]}\)：マス \((i, j)\) の直前までのマスに \(0\) か \(1\) を書き込んで数えるべきグリッドの途中までを生成する方法のうち、次の条件を満たすものの数。
  • \(\mathrm{flag}\) が \(1\) なら \(i\) 行目にここまでに書き込んだ数はすべて \(1\) であり、\(\mathrm{flag}\) が \(0\) ならそうでない。
  • \(\mathrm{mask}\) の下から \(j\) ビット目が \(1\) なら \(j\) 列目にここまでに書き込んだ数はすべて \(1\) であり、\(\mathrm{mask}\) の下から \(j\) ビット目が \(0\) ならそうでない。

これらの値を順に計算すれば \(O(2^{M} NM)\) 時間で答えが求まります。

実装例（C++。配列をメモリ制限に収めるため int を使います）

#include <iostream>
#include <vector>

using namespace std;

#define add(x, v) (x) += (v); if((x) >= MOD) (x) -= MOD;

const int MN = 18, MOD = 998244353;
int dp[MN + 1][MN + 1][2][1 << MN];

int main(){
    int N, M;
    cin >> N >> M;
    vector<string> X(N);
    for(int i = 0; i < N; ++i){
        cin >> X[i];
    }
    dp[0][0][1][(1 << M) - 1] = 1;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            for(int flag = 0; flag < 2; ++flag){
                for(int mask = 0; mask < 1 << M; ++mask){
                    if(X[i][j] != '1'){
                        add(dp[i][j + 1][0][mask & ~(1 << j)], dp[i][j][flag][mask]);
                    }
                    if(X[i][j] != '0' && (flag || mask & (1 << j))){
                        add(dp[i][j + 1][flag][mask], dp[i][j][flag][mask]);
                    }
                }
            }
        }
        for(int mask = 0; mask < 1 << M; ++mask){
            add(dp[i + 1][0][1][mask], dp[i][M][0][mask] + dp[i][M][1][mask]);
        }
    }
    long long ans = 0;
    for(int mask = 0; mask < 1 << M; ++mask){
        add(ans, dp[N][0][1][mask]);
    }
    cout << ans << endl;
}