#include <cstdio>
const int M = 5005;
const int MOD = 1e9+7;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,q,rk[M],t[M],a[M],b[M][M];char s[M];
signed main()
{
	n=read();m=read();q=read();
	for(int i=1;i<=m;i++) rk[i]=i;
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);int o=0;
		for(int j=1;j<=m;j++) b[j][i]=a[j]=s[j]-'0';
		for(int j=1;j<=m;j++) if(a[rk[j]]==0) t[++o]=rk[j];
		for(int j=1;j<=m;j++) if(a[rk[j]]==1) t[++o]=rk[j];
		for(int j=1;j<=m;j++) rk[j]=t[j];
	}
	for(int j=1;j<=m;j++) a[j]=0;
	for(int j=1;j<=m;j++) for(int i=n;i>=1;i--)
		a[j]=(2*a[j]+b[j][i])%MOD;
	for(int i=1;i<=n;i++) a[m+1]=(2*a[m+1]+1)%MOD;
	a[m+1]++;rk[m+1]=m+1;
	while(q--)
	{
		scanf("%s",s+1);int l=0,r=m+1;
		for(int i=1;i<=m;i++) if(s[rk[i]]=='1') {r=i;break;}
		for(int i=m;i>=1;i--) if(s[rk[i]]=='0') {l=i;break;}
		printf("%d\n",(r<l)?0:(a[rk[r]]-a[rk[l]]+MOD)%MOD);
	}
}

是 myy 的题呢 orz

我们先考虑 $m=1$ 的情况。

容易发现位运算存在这样的规律：

1. $\vee 1$ 和 $\wedge 0$ 会直接影响运算结果，前者使得值变为 $1$，后者使得值变为 $0$；
2. $\vee 0$ 和 $\wedge 1$ 对结果没有影响。

由上面两个结论可以知道，运算最后结果为 $1$，当且仅当存在至少一个 $\vee 1$ 操作，且最后一个 $\vee 1$ 操作在 $\wedge 0$ 操作之前。

看起来似乎还是不太好办？我们转化一下。

设操作序列中 $\vee=0$，$\wedge=1$。

同时我们设数字序列从下往上看得到的数为 $x$，操作序列从下往上看得到的数为 $y$，

这样我们可以转化条件：运算最后结果为 $1$，当且仅当 $x \gt y$。

感性理解一下，从高位向低位相同的位都不影响结果，而对于第一个不同的位，$x$ 对应的位为 $1$，$y$ 对应的位为 $0$ 时，意味着我们在这个位上执行了一次 $\vee 1$ 操作，根据前面的性质，易知这种情况下运算结果为 $1$，反之同理。

最后解集一定是这两个不等式之一：$x \gt y$（该位是 $1$） 或者是 $x \leq y$（该位是 $0$）。

这样我们就解决了 $m=1$ 的情况。

对于多个位的情况，我们需要将各个位的结果合并。

说白了就是解这样一个不等式组：

$$\begin{cases} x \gt a_1\\ x \leq a_2\\ x \leq a_3\\ x \gt a_4\\ \vdots \end{cases}$$

// Problem : P4424 [HNOI/AHOI2018]寻宝游戏
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P4424
// Author : StudyingFather
// Site : https://studyingfather.com
// Memory Limit : 500 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <iostream>
#include <string>
#include <algorithm>
#define MOD 1000000007
using namespace std;
struct node
{
 string s;
 int id;
 bool operator<(const node&a)const
 {
  return s>a.s||(s==a.s&&id<a.id);
 }
}p[5005];
string a[1005];
long long res[5005];
int main()
{
 ios::sync_with_stdio(false);
 int n,m,q;
 cin>>n>>m>>q;
 for(int i=1;i<=n;i++)
  cin>>a[i];
 for(int i=0;i<m;i++)
 {
  p[i].id=i;
  for(int j=n;j;j--)
  {
   a[j][i]-='0';
   res[i]=(res[i]*2+a[j][i])%MOD;
   p[i].s.push_back(a[j][i]);
  }
 }
 p[m].id=m;
 p[m+1].id=m+1;
 for(int j=n;j;j--)
 {
  res[m]=(res[m]*2+1)%MOD;
  p[m].s.push_back(1);
 }
 res[m]++;
 sort(p,p+m+1);
 while(q--)
 {
  string str;
  cin>>str;
  int l=0,r=m+1;
  for(int i=m;i;i--)
   if(str[p[i].id]=='1')
   {
    l=i;
    break;
   }
  for(int i=0;i<=m;i++)
   if(str[p[i].id]=='0')
   {
    r=i;
    break;
   }
  cout<<(l>r?0:(res[p[l].id]-res[p[r].id]+MOD)%MOD)<<endl;
 }
 return 0;
}

对每一位考虑是从哪个位置贡献来的，可以得到 $nm$ 个后缀。

后缀总长度为 $n^2m$，无法存储。考虑对于所有后缀建 trie，空间就只有 $nm$ 级别了。

若 trie 上一个结点到根的 $cnt$ 总和是 $m$ 则以这个点结尾时合法的，方案数为 $2$ 的幂次。此时可以知道它对应的 $01$ 串，哈希记录。