三进制状压。

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353; 
const int N=210,M=43046723;
int n,m,i,j,p[N],s[N],k,x,y,l,ans,pre,now;
char t[N][N],a[N][N];
int b[M],B[M],C[M],cnt,cc;
int dp[2][M];
inline bool fun(int x)
{
	int i,t=-1;
	for (i=1;i<=m;i++)
	{
		if (x%3==t) return false;
		t=x%3;
		x/=3;
	}
	return true;
}
inline bool check(int x,int i)
{
	int j=1,p;
	for (p=1;p<=m;p++)
	{
		if (a[i][j]!='?'&&x%3!=a[i][j]-'1') return false;
		x/=3;
		j++;
	}
	return true;
}
inline bool ck(int x,int y)
{
	int i;
	for (i=1;i<=m;i++)
	{
		if (x%3==y%3) return false;
		x/=3;
		y/=3; 
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++) scanf("%s",t[i]+1);
	if (m>n)
	{
		for (i=1;i<=m;i++)
		{
			for (j=1;j<=n;j++) a[i][j]=t[j][i];
		}
		swap(n,m);
	}
	else
	{
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=m;j++) a[i][j]=t[i][j];
		}
	}
	pre=0;
	now=1;
	p[0]=1;
	for (i=1;i<=m;i++) p[i]=p[i-1]*3;
	for (i=0;i<p[m];i++)
	{
		if (fun(i)) b[++k]=i;
	}
	for (i=1;i<=k;i++) 
	{
		if (check(b[i],1)) dp[pre][i]=1,B[++cnt]=i;
	}
	for (i=2;i<=n;i++)
	{
		for (j=1;j<=k;j++)
		{
			dp[now][j]=0;
			x=b[j];
			if (!check(x,i)) continue;
			C[++cc]=j;
			for (l=1;l<=cnt;l++)
			{
				y=b[B[l]];
				if (ck(x,y)) dp[now][j]=(dp[now][j]+dp[pre][B[l]])%mod;
			}
		}
		cnt=cc;
		for (j=1;j<=cnt;j++) B[j]=C[j]; 
		cc=0;
		pre=now;
		now=1-pre;
	}
	for (i=1;i<=k;i++) ans=(ans+dp[pre][i])%mod;
	printf("%d",ans);
	return 0;
}